poj 2481 cows（树状数组）

题意：给出n个牛的坐标，i牛的坐标为[Si,Ei],j牛的坐标为[Sj,Ej]，若Si<=Sj,Ej<=Ei并且Ei-Si>Ej-Sj，则牛i比牛j强壮，现在呀要求出每个牛比它强壮的牛的数量。

分析：这道题和poj2352类似，poj 2352是要求在某点左下角的点有多少个，这一题则可以看成是求在某点左上角的点的个数，按纵坐标从大到小排序，横坐标从小到大排序，然后用树状数组求在该点左边的点的数量即可。需要注意的是，对于相同的点，不需要重复计算，直接赋值就行了，不然会超时的。

不过这道题我有一点纳闷的就是，输出的时候我用if（）来判断下标确定是该输出空格还是换行的时候居然超时了，改成不用if（）判断的输出时就能过，这实在是坑爹。。。。什么破数据呀，用的着这样卡么！！

AC代码：

 1         #include<stdio.h>
 2         #include<string.h>
 3         #include<algorithm>
 4         using namespace std;
 5         #define N 100100
 6         int d[N],cnt[N];
 7         struct node{
 8             int x,y,i;
 9             bool operator <(const node &a)const{
10                 if(y==a.y)
11                     return x<a.x;
12                 return y>a.y;
13             }
14         }s[N];
15         int n;
16         int lowbit(int x)
17         {
18             return x&(-x);
19         }
20         void update(int x,int num)
21         {
22             while(x<=n)
23             {
24                 d[x]+=num;
25                 x+=lowbit(x);
26             }
27         }
28         int GetSum(int x)
29         {
30             int s=0;
31             while(x>0)
32             {
33                 s+=d[x];
34                 x-=lowbit(x);
35             }
36             return s;
37         }
38         int main()
39         {
40             int i;
41             while(scanf("%d",&n)&&n)
42             {
43                 for(i=0;i<n;i++)
44                 {
45                     scanf("%d%d",&s[i].x,&s[i].y);
46                     s[i].x++;
47                     s[i].y++;
48                     s[i].i=i;
49                 }
50                 sort(s,s+n);
51                 memset(d,0,sizeof(d));
52                 for(i=0;i<n;i++)
53                 {
54                     if(i>0&&s[i].x==s[i-1].x&&s[i].y==s[i-1].y)
55                         cnt[s[i].i]=cnt[s[i-1].i];
56                     else
57                         cnt[s[i].i]=GetSum(s[i].x);
58                     update(s[i].x,1);
59                 }
60                 for(i=0;i<n;i++)
61                 {
62                     if(i==n-1)
63                         printf("%d
",cnt[i]);
64                     else
65                         printf("%d ",cnt[i]);
66                 }
67             }
68             return 0;
69         }

View Code