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

 int find_kth(int k)

 {

     int ans = , cnt = , i;

     for (i = ; i >= ; i--)/

     {

         ans += ( << i);

         if (ans >= maxn|| cnt + c[ans] >= k)

             ans -= ( << i);

         else

             cnt += c[ans];

     }

     return ans + ;

 }

题意：

口袋里可以放进不同大小的糖果，也可以拿出不同大小的糖果。查询过程中第k小的糖果体积是多少

输入T，有T组，接下来是输入m次操作

m行输入op和x

当op等于1的时候，放进x大小的糖果

当op等于2的时候，拿进x大小的糖果

当op等于3的时候，查询第x小的糖果，并输出答案

思路：二分+树状数组（比赛时限）

这里写一个优化的树状数组的写法

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<string>

 #define mem(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 #define ll long long

 #define lowbit(b) b&(-b)

 using namespace std;

 const int maxn=1e5+;

 int c[maxn],f[];

 inline int read() {

     char ch = getchar(); int x = , f = ;

     while(ch < '' || ch > '') {

         if(ch == '-') f = -;

         ch = getchar();

     } while('' <= ch && ch <= '') {

         x = x *  + ch - '';

         ch = getchar();

     } return x * f;

 }

 inline void updata(int x, int y){

     for (int i = x; i <= maxn; i += lowbit(i)){

         c[i] += y;

     }

 }

 int main()

 {

 int t,i;f[]=;

 for(i=;i<=;i++){

     f[i]=f[i-]*;

 }

     t=read();

     while(t--){

         for(i=;i<maxn;i++){c[i]=;}

         int m;

        m=read();

         for(i=;i<m;i++){

             int op,x;

             op=read();x=read();

             if(op==){

                 updata(x,);

             }

             else if(op==){

                 updata(x,-);

             }

             else{

                 int ans=,sum=,j;

                 for(j=;j>=;j--){

                     ans+=f[j];

                     if(ans>=maxn || sum+c[ans]>=x){

                         ans-=f[j];

                     }

                     else{

                         sum+=c[ans];

                     }

                 }

                 printf("%d\n",ans+);

             }

         }

     }

     return ;

 }

 /*

 2

 3

 1 2

 1 2

 3 1

 4

 1 2

 1 3

 2 2

 3 1

 */