hdu 2852 树状数组

查找比a大的第k小的元素其实就是查找第sum(a)+k小的元素，用不需要二分的树状数组就可以了。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 100000;
 7 int c[N];
 8 
 9 int lb( int i )
10 {
11     return i & -i;
12 }
13 
14 void update( int i, int v )
15 {
16     while ( i < N )
17     {
18         c[i] += v;
19         i += lb(i);
20     }
21 }
22 
23 int sum( int i )
24 {
25     int ans = 0;
26     while ( i )
27     {
28         ans += c[i];
29         i -= lb(i);
30     }
31     return ans;
32 }
33 
34 int sumk( int k )
35 {
36     int ans = 0, cnt = 0;
37     for ( int i = 20; i >= 0; i-- )
38     {
39         ans += ( 1 << i );
40         if ( ans >= N - 1 || cnt + c[ans] >= k )
41         {
42             ans -= ( 1 << i );
43         }
44         else
45         {
46             cnt += c[ans];
47         }
48     }
49     return ans + 1;
50 }
51 
52 int main ()
53 {
54     int n;
55     while ( scanf("%d", &n) != EOF )
56     {
57         memset( c, 0, sizeof(c) );
58         for ( int i = 1; i <= n; i++ )
59         {
60             int op, x, y;
61             scanf("%d", &op);
62             if ( op == 0 )
63             {
64                 scanf("%d", &x);
65                 update( x, 1 );
66             }
67             else if ( op == 1 )
68             {
69                 scanf("%d", &x);
70                 if ( sum(x) - sum( x - 1 ) > 0 )
71                 {
72                     update( x, -1 );
73                 }
74                 else
75                 {
76                     printf("No Elment!
");
77                 }
78             }
79             else
80             {
81                 scanf("%d%d", &x, &y);
82                 int k = sum(x) + y;
83                 if ( k <= sum( N - 1 ) )
84                 {
85                     printf("%d
", sumk(k));
86                 }
87                 else
88                 {
89                     printf("Not Find!
");
90                 }
91             }
92         }
93     }
94     return 0;
95 }