poj 2352 树状数组 OR Treap

由于星星是按照y从小到大，y相同x从小到大排好序的（其实没排好也没关系，我们有sort和cmp大法），所以只要不断地求某个位置的前缀和就好了，可以用树状数组或Treap来维护。

树状数组：

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

Treap：由于有重复元素所以结点多维护了一个cnt，表示x为该值的星星个数。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <ctime>
  6 using namespace std;
  7 
  8 struct Node 
  9 {
 10     Node * ch[2];
 11     int v, r, size, cnt;
 12     int cmp( int x )
 13     {
 14         if ( x == v ) return -1;
 15         return x < v ? 0 : 1;
 16     }    
 17     void maintain()
 18     {
 19         size = cnt;
 20         if ( ch[0] != NULL ) size += ch[0]->size;
 21         if ( ch[1] != NULL ) size += ch[1]->size;
 22     }
 23 };
 24 
 25 void rotate( Node * & o, int d )
 26 {
 27     Node * k = o->ch[d ^ 1];
 28     o->ch[d ^ 1] = k->ch[d];
 29     k->ch[d] = o;
 30     o->maintain();
 31     k->maintain();
 32     o = k;
 33 }
 34 
 35 void insert( Node * & o, int x )
 36 {
 37     if ( o == NULL )
 38     {
 39         o = new Node();
 40         o->ch[0] = o->ch[1] = NULL;
 41         o->v = x;
 42         o->r = rand();
 43         o->size = o->cnt = 1;
 44     }
 45     else
 46     {
 47         int d = o->cmp(x);
 48         if ( d == -1 )
 49         {
 50             o->cnt++;
 51             o->size++;
 52         }
 53         else
 54         {
 55             insert( o->ch[d], x );
 56             if ( o->ch[d]->r > o->r )
 57             {
 58                 rotate( o, d ^ 1 );
 59             }
 60             o->maintain();
 61         }
 62     }
 63 }
 64 
 65 int ranker( Node * o, int x, int sum )
 66 {
 67     int d = o->cmp(x);
 68     if ( d == -1 )
 69     {
 70         return sum + ( o->ch[0] == NULL ? 0 : o->ch[0]->size ) + o->cnt;
 71     }
 72     else if ( d == 0 )    
 73     {
 74         return ranker( o->ch[0], x, sum );
 75     }
 76     else
 77     {
 78         int tmp = ( o->ch[0] == NULL ? 0 : o->ch[0]->size );
 79         return ranker( o->ch[1], x, sum + tmp + o->cnt );
 80     }
 81 }
 82 
 83 const int N = 15001;
 84 int ans[N];
 85 
 86 int main ()
 87 {
 88     int n;
 89     while ( scanf("%d", &n) != EOF )
 90     {
 91         Node * root = NULL;
 92         memset( ans, 0, sizeof(ans) );
 93         for ( int i = 0; i < n; i++ )
 94         {
 95             int x, y;
 96             scanf("%d%d", &x, &y);
 97             insert( root, x );
 98             ans[ranker( root, x, 0 )]++;
 99         }
100         for ( int i = 1; i <= n; i++ )
101         {
102             printf("%d
", ans[i]);
103         }
104     }
105     return 0;
106 }