HDU-1541 POJ-2352 Stars

 1 #include <iostream>
 2 #include <cstring>
 3 #define pb push_back
 4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 5 #define INF 0x3f3f3f3f
 6 #define sz size()
 7 
 8 using namespace std;
 9 typedef long long ll;
10 
11 const int maxn = 1 << 18;
12 
13 int n, dat[2*maxn];
14 
15 void init(int n_)
16 {
17     n = (1 << 18)-2;
18     memset(dat,0,sizeof(dat));
19 }
20 
21 //更新第k(0-index)个值为a
22 void update(int k)
23 {
24     k += n+1;
25     dat[k] ++;
26     while(k>0)
27     {
28         k = (k-1)/2;
29         dat[k] = dat[k*2+1]+dat[k*2+2];
30     }
31 }
32 
33 //求(a,b)val
34 //query(a,b,0,0,n)
35 int query(int a,int b,int k,int l,int r)
36 {
37     //不相交
38     if(r<a || b<l) return 0;
39 
40     if(a<=l && r<=b) {return dat[k];}
41     else
42     {
43         int vl = query(a,b,k*2+1,l,(l+r)/2);
44         int vr = query(a,b,k*2+2,(l+r)/2+1,r);
45         
46         return vl+vr;
47     }
48     return -1;//error
49 }
50 
51 int readint()
52 {
53     int t;
54     scanf("%d",&t);
55     return t;
56 }
57 
58 int main()
59 {
60     int N;
61     while(scanf("%d",&N)!=EOF)
62     {
63         init(n);
64         int rnt[15002];
65         memset(rnt,0,sizeof(rnt));
66         _for(i,0,N)
67         {
68             int x = readint();
69             rnt[query(0,x,0,0,n)] ++;
70             update(x);
71             readint();
72         }
73         _for(i,0,N)
74             printf("%d
",rnt[i]);
75     }
76     return 0;
77 }