HDU 2852 KiKi's K-Number 树状数组 + 二分

一共最多才100000个数，并且数值范围0~100000。

树状数组 C[i] 记录数值为 i 的数有多少个。

删除时如果Query( a ) - Query( a - 1 ) == 0 则该数不存在。

求大于a的第K大数只需要对大于a的数二分查找一下，Query( MAXN ) - Query(a)为大于 a 的数的总个数，如果小于K 则不存在。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 100010;
 9 
10 int Q;
11 int C[MAXN];
12 
13 int lowbit( int x )
14 {
15     return x & (-x);
16 }
17 
18 void Update( int x, int val )
19 {
20     while ( x < MAXN )
21     {
22         C[x] += val;
23         x += lowbit(x);
24     }
25     return;
26 }
27 
28 int Query( int x )
29 {
30     int res = 0;
31     while ( x > 0 )
32     {
33         res += C[x];
34         x -= lowbit(x);
35     }
36     return res;
37 }
38 
39 int BiSearch( int l, int r, int val, int zuo )
40 {
41     int ans = -1;
42     while ( l <= r )
43     {
44         int mid = ( l + r ) >> 1;
45         int tmp = Query( mid ) - Query( zuo );
46         //printf( "%d %d
", mid, tmp );
47         if ( tmp >= val )
48         {
49             r = mid - 1;
50             ans = mid;
51         }
52         else l = mid + 1;
53     }
54     return ans;
55 }
56 
57 int main()
58 {
59     while ( ~scanf( "%d", &Q ) )
60     {
61         memset( C, 0, sizeof(C) );
62         while ( Q-- )
63         {
64             int op, a, b;
65             scanf( "%d", &op );
66             switch( op )
67             {
68             case 0:
69                 scanf( "%d", &a );
70                 Update( a, 1 );
71                 break;
72 
73             case 1:
74                 scanf( "%d", &a );
75                 if ( Query( a ) - Query( a - 1 ) == 0 ) puts("No Elment!");
76                 else Update( a, -1 );
77                 break;
78 
79             case 2:
80                 scanf( "%d%d", &a, &b );
81                 if ( Query( MAXN - 1 ) - Query( a ) < b ) puts("Not Find!");
82                 else
83                 {
84                     int ans = BiSearch( a, MAXN - 1, b, a );
85                     printf( "%d
", ans );
86                 }
87                 break;
88             }
89         }
90     }
91     return 0;
92 }