19市赛 树状数组 第k个小的糖果

 1 #include<iostream>  
 2 #include<cstring>  
 3 #include<cstdio>  
 4 #include<cmath>  
 5 #include<algorithm>  
 6 #include<string>  
 7 #define mem(a,b) memset(a,b,sizeof(a))  
 8 #define inf 0x3f3f3f3f  
 9 #define ll long long  
10 #define lowbit(b) b&(-b)  
11 using namespace std;  
12 const int maxn=1e5+10;  
13 int c[maxn],f[20];  
14 inline int read() {  
15     char ch = getchar(); int x = 0, f = 1;  
16     while(ch < ‘0‘ || ch > ‘9‘) {  
17         if(ch == ‘-‘) f = -1;  
18         ch = getchar();  
19     } while(‘0‘ <= ch && ch <= ‘9‘) {  
20         x = x * 10 + ch - ‘0‘;  
21         ch = getchar();  
22     } return x * f;  
23 }  
24 inline void updata(int x, int y){  
25     for (int i = x; i <= maxn; i += lowbit(i)){  
26         c[i] += y;  
27     }  
28 }  
29 int main()  
30 {  
31 int t,i;f[0]=1;  
32 for(i=1;i<=17;i++){  
33     f[i]=f[i-1]*2;  
34 }  
35     t=read();  
36     while(t--){  
37         for(i=0;i<maxn;i++){c[i]=0;}  
38         int m;  
39        m=read();  
40         for(i=0;i<m;i++){  
41             int op,x;  
42             op=read();x=read();  
43             if(op==1){  
44                 updata(x,1);  
45             }  
46             else if(op==2){  
47                 updata(x,-1);  
48             }  
49             else{  
50                 int ans=0,sum=0,j;  
51                 for(j=17;j>=0;j--){  
52                     ans+=f[j];  
53                     if(ans>=maxn || sum+c[ans]>=x){  
54                         ans-=f[j];  
55                     }  
56                     else{  
57                         sum+=c[ans];  
58                     }  
59                 }  
60                 printf("%d\n",ans+1);  
61             }  
62         }  
63     }  
64     return 0;  
65 }  
66 /* 
67 2 
68 3 
69 1 2 
70 1 2 
71 3 1 
72 4 
73 1 2 
74 1 3 
75 2 2 
76 3 1 
77 */