HDU2852 KiKi's K-Number 树状数组+二分 - c++编程基础

这题就是给了你三种操作，

1：往容器中一个元素 x

2:：把容器中的元素x删除

3：查询比 x大的第k个数

想法：添加元素跟删除元素直接是以数本身为序号然后以 value值为1和-1即可，相当于计数，至于找比x第k个大的数，那就看看当前往后数k个数的第一个数是哪个就可以了，一开始直接找出来，然后往后暴力的扫了一遍，结果错了，没关系，反应很快，直接改了个二分查找，然后就过了，弄清楚如何建立这个树状数组即可

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                  > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; const int N = 100000 + 10; int n; int c[N]; void clear() { memset(c,0,sizeof(c)); } int lowbit(int x) { return x&(-x); } //设原始矩阵为a,将a[i]加上val时对c所做的修改 void add(int i, int val) { while (i <= N) { c[i] += val; i += lowbit(i); } } //求前i项元素的和 int get_sum(int i) { int sum = 0; while (i > 0) { sum += c[i]; i -= lowbit(i); } return sum; } void cal(int a,int k) { int sum = get_sum(a); bool flag = false; int l = a + 1; int r = N; while(l < r) { int mid = (l + r)/2; int tmp = get_sum(mid); if(tmp < sum + k) l = mid + 1; else r = mid; } if(get_sum(l) >= k + sum) { printf("%d\n",l); } else puts("Not Find!"); } int main() { int n; while(scanf("%d",&n) == 1) { clear(); int x; for(int i=0;i