今天联系树状数组，但是我发现我真的很笨，做了好几道了还是不熟。这个题和前边的也没什么分别，是说每个牛有一个区间[s,e],两个牛[s1,e1], [s2,e2]，当s1<=s2并且e1>=e2并且e1-s1>e2-s2时，我们说牛1比牛2强，给N个牛的区间，对于每个牛，输出比这个牛强的牛的个数。
还是需要预处理，先对每个牛的e进行降序排序，e相同时对s进行升序排列，这样循环时可以保证后边的牛绝对不比前边的牛强。在循环时，只需找出比当前牛s小的牛的个数。如果遇到特殊情况，即两个牛区间完全一样，赋值就可以了。哎，加油吧~
Code：
1 #include<iostream>
2 #include<algorithm>
3 #include<map>
4 #define MAX 100002
5 using namespace std;
6 int c[MAX],ans[MAX],n,imax;
7 struct cow
8 {
9 int l,r,id;
10 }a[MAX];
11 bool cmp(cow a,cow b){
12 if(a.r==b.r) //如果两个牛区间右边界相同，按左边界的升序排列
13 return a.l<b.l;
14 return a.r>b.r; //按右边界的降序排列
15 }
16 int lowbit(int t){
17 return t&(t^(t-1));
18 }
19 int sum(int t){
20 int total=0;
21 while(t>0){
22 total+=c[t];
23 t-=lowbit(t);
24 }
25 return total;
26 }
27 void modify(int posi,int key){
28 while(posi<=imax){
29 c[posi]+=key;
30 posi+=lowbit(posi);
31 }
32 }
33 int main()
34 {
35 int i,j,k,n;
36 while(scanf("%d",&n),n){
37 memset(c,0,sizeof(c));
38 imax=0;
39 for(i=1;i<=n;i++){
40 scanf("%d%d",&a[i].l,&a[i].r);
41 a[i].id=i; //每个牛有个id防止排序完顺序变乱
42 ++a[i].l; ++a[i].r;
43 if(imax<a[i].l) imax=a[i].l; //用imax表示右边界最大值，即求和时的边界
44 }
45 sort(a+1,a+n+1,cmp);
46 for(i=1;i<=n;++i){
47 if(i==1){
48 ans[a[i].id]=sum(a[i].l); //这里注意是ans[a[i].id]而不是ans[i]
49 modify(a[i].l,1);
50 }
51 else{
52 if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) //如果两个牛完全相同，直接赋值
53 ans[a[i].id]=ans[a[i-1].id];
54 else
55 ans[a[i].id]=sum(a[i].l); //否则找出左边界l比这个牛小的
56 modify(a[i].l,1);
57 }
58 }
59 for(i=1;i<n;++i)
60 printf("%d ",ans[i]);
61 printf("%d\n",ans[i]);
62 }
63 }
64