【bzoj3224】【Tyvj 1728】普通平衡树树状数组

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入$x$数
2. 删除$x$数(若有多个相同的数，因只删除一个)
3. 查询$x$数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为$x$的数
5. 求$x$的前驱(前驱定义为小于$x$，且最大的数)
6. 求$x$的后继(后继定义为大于$x$，且最小的数)

数据范围：操作数$≤10^5$，$x≤10^9$。

这一题用平衡树做的方法是显然的，然而平衡树太长太慢，我们考虑写一个优美一点的算法。

首先先离散化所有读入的数（别离散化操作4！！！！）

然后，插入和删除操作显然（直接在离散化后的x处，赋值+1或者-1即可）

查询某个数的排名也是显然的。

考虑查询排名为$x$如何高速完成，此处不妨设$x$为正整数。

我们求一个最小的$p$，使得$2^p≥cnt$，其中$cnt$为树状数组的长度。

设当前访问到的点为$id$（初始为$0$）

我们每次查询$a[id+2^p]$上的值是否小于$x$，如果是$x$，那么$id+=2^p$，然后$x-=a[id]$。

然后p--即可。

最后输出$id+1$即是第$k$大的数。

求前驱和后继：先求出给出的数是第几大的，然后$+1$或$-1$即可。

代码奇短

 #include<bits/stdc++.h>

 #define M 200000

 #define lowbit(x) ((x)&(-x))

 using namespace std;

 int a[M]={},c[M]={},n,cnt=,m;

 int op[M]={},b[M]={};

 void add(int x,int k){for(;x<=n;x+=lowbit(x)) a[x]+=k;}

 int sum(int x){int k=;for(;x;x-=lowbit(x)) k+=a[x]; return k;}

 int getkth(int k){

     int id=;

     for(int i=n;i;i>>=){

         if(k>a[id+i])

         k-=a[id+i],id+=i;

     }

     return id+;

 }

 int main(){

     scanf("%d",&m);

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

         scanf("%d%d",op+i,b+i);

         if(op[i]!=) c[++cnt]=b[i];

     }

     sort(c+,c+cnt+);

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

     if(op[i]!=) b[i]=lower_bound(c+,c+cnt+,b[i])-c;

     for(n=;n<=cnt;n<<=);

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

         if(op[i]==) add(b[i],);

         if(op[i]==) add(b[i],-);

         if(op[i]==) printf("%d\n",sum(b[i]-)+);

         if(op[i]==) printf("%d\n",c[getkth(b[i])]);

         if(op[i]==) printf("%d\n",c[getkth(sum(b[i]-))]);

         if(op[i]==) printf("%d\n",c[getkth(sum(b[i])+)]);

     }

 }

巴特西

【bzoj3224】【Tyvj 1728】普通平衡树树状数组

最新文章

热门文章

巴特西

【bzoj3224】【Tyvj 1728】 普通平衡树 树状数组

最新文章

热门文章

【bzoj3224】【Tyvj 1728】普通平衡树树状数组