hdu 2852 KiKi's K-Number (线段树)-白红宇

hdu 2852 KiKi's K-Number (线段树)

阅读量：5744 次

发布时间：2019-06-18

本文共 1284 字，大约阅读时间需要 4 分钟。

题意：

　　一个容器，三种操作：

　　　　（1）加入一个数 e

　　　　（2）删除一个数 e，如果不存在则输出 No Elment!

　　　　（3）查询比a大的数中的第k小数，不存在就输出 Not Find!

解法：

　　关于第三点，可以先查询小于等于a的数的个数cnt，然后直接查询第cnt+k小数就行了。

　　二分+树状数组或者主席树（有点杀鸡用牛刀的感觉。。。）也是可以做的 _(:з」∠)_

code：线段树

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #define ll long long11 12 using namespace std;13 14 const int N=1e5+7;15 16 int L[N*4],R[N*4],cnt[N*4];17 18 inline void bulidtree(int l,int r,int k){19 L[k]=l; R[k]=r;20 cnt[k]=0;21 if (l==r) return;22 int mid=(l+r)>>1;23 bulidtree(l,mid,k<<1);24 bulidtree(mid+1,r,(k<<1)|1);25 }26 27 inline void update(int p,int d,int k){28 cnt[k]+=d;29 if (L[k]==R[k]) return;30 int mid=(L[k]+R[k])>>1;31 if (p<=mid) update(p,d,k<<1);32 else update(p,d,(k<<1)|1);33 }34 35 inline int query(int x,int y,int k){36 if (L[k]==x && R[k]==y)37 return cnt[k];38 int mid=(L[k]+R[k])>>1;39 if (y<=mid) return query(x,y,k<<1);40 else if (x>mid) return query(x,y,(k<<1)|1);41 else return query(x,mid,k<<1)+query(mid+1,y,(k<<1)|1);42 }43 44 inline int find(int x,int k){45 if (cnt[k]

转载于:https://www.cnblogs.com/without-ACM/p/5935063.html

你可能感兴趣的文章