POJ——T2352 Stars

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 #define lowbit(x) (x&(-x))
 5 
 6 using namespace std;
 7 
 8 const int N(15015);
 9 const int N_(32015);
10 int n;
11 struct TypeNodeStar
12 {
13     int x,y;
14 }star[N];
15 
16 bool cmp(TypeNodeStar a,TypeNodeStar b)
17 {
18     if(a.x!=b.x) return a.x<b.x;
19     return a.y<b.y;
20 }
21 
22 int c[N_];
23 int ans[N],t[N_];
24 
25 int query(int x)
26 {
27     int ans=0;
28     for(;x;x-=lowbit(x)) ans+=t[x];
29     return ans;
30 }
31 
32 void insert(int x)
33 {
34     for(;x<=N_;x+=lowbit(x)) t[x]++;
35 }
36 
37 int main()
38 {
39     scanf("%d",&n);
40     for(int i=1;i<=n;i++)
41     {
42         scanf("%d%d",&star[i].x,&star[i].y);
43         star[i].x++; star[i].y++;
44     }
45     sort(star+1,star+n+1,cmp);
46     for(int i=1;i<=n;i++)
47     {
48         int tmp=query(star[i].y);
49         insert(star[i].y);
50         ans[tmp]++;
51     }
52     for(int i=0;i<n;i++) printf("%d\n",ans[i]);
53     return 0;
54 }