poj 2352 Stars

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=15000+5;
 6 const int maxd=32000+5;
 7 int c[maxd];
 8 int ans[maxn];
 9 int lowbit(int x)
10 {
11     return x&-x;
12 }
13 int sum(int x)
14 {
15     int ret=0;
16     while(x>0)
17     {
18         ret+=c[x];
19         x-=lowbit(x);
20     }
21     return ret;
22 }
23 void add(int x,int inc)
24 {
25     while(x<=maxd)
26     {
27         c[x]+=inc;
28         x+=lowbit(x);
29     }
30 }
31 int main()
32 {
33     int n;
34     while(scanf("%d",&n)!=EOF)
35     {
36         memset(ans,0,sizeof(ans));
37         memset(c,0,sizeof(c));
38         int x,y;
39         scanf("%d%d",&x,&y);
40         ans[0]++;
41         add(x+1,1);
42         int tmp=0,tmpx=x,tmpy=y;
43       for(int i=1;i<n;i++)
44         {
45            scanf("%d%d",&x,&y);
46            if(tmpx==x&&tmpy==y)
47             ans[tmp]++;
48             else
49             {
50                 tmp=sum(x+1);
51                 ans[tmp]++;
52             }
53               add(x+1,1);
54               tmpx=x,tmpy=y;
55         }
56         for(int i=0;i<n;i++)
57             printf("%d
",ans[i]);
58     }
59     return 0;
60 }