poj2481 Cows 树状数组

解题思路：

这道题对每组数据进行查询，是树状数组的应用。对于二维的树状数组，

首先想到排序。现在对输入的数据按右值从大到小排序，在右值相同的情况下，左值从小到大排序。则对于每头牛，它前面的牛的右区间至少在它的右面，

用树状数组可以快速查询出这头牛前面的左值不大于当前牛的牛的个数。

代码：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 #define maxn 100010
 8 int c[maxn];
 9 class node
10 {
11    public:
12    int s,e;
13    int index;
14 };
15 node Node[maxn];
16 int n;
17 int cnt[maxn];
18 
19 bool cmp(node a ,node b)
20 {
21   if(a.e == b.e) return a.s< b.s;
22   else  return a.e>b.e;
23 }
24 
25 int lowbit(int x)
26 {
27     return x&(-x);
28 }
29 void add(int i,int val)
30 {
31    while(i<=n)
32    {
33        c[i]+=val;
34        i+=lowbit(i);
35    }
36 }
37 int sum(int i)
38 {
39     int  s=0;
40     while(i>0)
41     {
42        s+=c[i];
43        i-=lowbit(i);
44     }
45     return s;
46 }
47 int main()
48 {
49      while(scanf("%d",&n)!=EOF && n)
50      {
51         for(int i=1;i<=n;i++)
52         {
53            scanf("%d%d",&Node[i].s,&Node[i].e);
54            Node[i].index=i;
55         }
56      
57      sort(Node+1,Node+1+n,cmp);
58   //   for(int i=1;i<=n;i++)
59     //         cout<<Node[i].s<<" "<<Node[i].e<<endl;
60      memset(c,0,sizeof(c));
61      memset(cnt,0,sizeof(cnt));
62 
63      cnt[Node[1].index]=0;
64      add(Node[1].s+1,1);
65 
66      for(int i=2;i<=n;i++)
67      {
68        if(Node[i].e==Node[i-1].e && Node[i].s == Node[i-1].s)
69         cnt[Node[i].index]=cnt[Node[i-1].index];
70         else
71          cnt[Node[i].index]=sum(Node[i].s+1);
72          add(Node[i].s+1,1);
73      }
74      cout<<cnt[1];
75      for(int i=2;i<=n;i++)
76         cout<<" "<<cnt[i];
77         cout<<endl;
78     }
79    return 0;
80 }