POJ 2352 Stars | 树状数组

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define N 40010
 5 using namespace std;
 6 int t[N],n,x,y,sum[N];
 7 void modify(int x)
 8 {
 9     while (x<N)
10     t[x]++,x+=x&-x;
11 }
12 int query(int x)
13 {
14     int ret=0;
15     while (x>0)
16     ret+=t[x],x-=x&-x;
17     return ret;
18 }
19 int main()
20 {
21     scanf("%d",&n);
22     for (int i=1;i<=n;i++)
23     {
24     scanf("%d%d",&x,&y);
25     sum[query(x+1)]++;
26     modify(x+1);
27     }
28     for (int i=0;i<n;i++)
29     printf("%d
",sum[i]);
30     return 0;
31 }