题解 P3369 【【模板】普通平衡树】
skydogli
·
·
题解
## （权值）线段树
~~如果你是不会线段树就来学平衡树的神仙，那对不起，下一篇吧~~
纵观6种操作，虽然我们不能用普通的线段树，但是发现这些操作对位置没有要求，所以我们可以使用用权值线段树完成，接下来我们一一分析：
- $1,$插入操作，把线段树中区间包含x的节点的sum++，单次复杂度$O(log_2V)$($V$表示线段树开了多大，下同）
- $2,$删除操作，把线段树中区间包含x的节点的sum--，单次复杂度$O(log_2V)
-
3,$求一个数的排名，求线段树小于x的数的个数，最后加$1$，单次复杂度$O(log_2V)
-
4,$求排名为k的数，每次判断，如果左子树的数的个数大于k，往左子树中找，否则往右子树中找，单次复杂度$O(log_2V)
-
5,$求前驱，就是在线段树中找第一个比x小的数，当右子树有满足的直接输出，可以这么感性理解:从右往左找，只要找到一个就是答案，所以只会到达底层1次，最大值比x小的区间可以O(1)判断是否有答案，所以复杂度也是$O(log_2V)
-
6,$求后继，就是在线段树中找第一个比x大的数，同上，复杂度$O(log_2V)
$Code:
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define rint register int
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
rint a=0,fh=1;
register char c=getchar();
while(c>'9'||c<'0'){if(c=='-')fh=-1;c=getchar();}
while('0'<=c&&c<='9'){
a=a*10+c-'0';
c=getchar();
}
return a*fh;
}//快读
#define Ls (x<<1)
#define Rs (x<<1|1)
#define MN 100005
int x[MN],v[MN],sum[MN<<2],op[MN],N,n;
//x，op：离线做，先记录操作 v:用于离散化
//sum:线段树中这个节点表示的区间有几个数
void Ins(int x,int l,int r,int loc,int v){
sum[x]+=v;
if(l==r)return;
rint mid=(l+r)>>1;
if(loc<=mid) Ins(Ls,l,mid,loc,v);
else Ins(Rs,mid+1,r,loc,v);
}//插入或删除一个数
int query(int x,int l,int r,int e){
if(l>e) return 0;
if(r<=e)return sum[x];
rint mid=(l+r)>>1;
return query(Ls,l,mid,e)+query(Rs,mid+1,r,e);
}//求小于e的数的个数
int kth(int x,int l,int r,int k){
if(l==r)return l;
rint mid=(l+r)>>1;
return (sum[Ls]>=k)?kth(Ls,l,mid,k):kth(Rs,mid+1,r,k-sum[Ls]);//注意往右子树找时k要先减去左子树的数的个数
}//求第K大
int pre(int x,int l,int r,int loc){
if(!sum[x]||l>=loc)return -1;
if(l==r) return l;
rint mid=(l+r)>>1,Rans=pre(Rs,mid+1,r,loc);
if(Rans!=-1) return Rans;
return pre(Ls,l,mid,loc);
}//前驱
int suf(int x,int l,int r,int loc){
if(!sum[x]||r<=loc) return -1;
if(l==r)return l;
rint mid=(l+r)>>1,Lans=suf(Ls,l,mid,loc);
if(Lans!=-1) return Lans;
return suf(Rs,mid+1,r,loc);
}//后继
int main(){
n=read();
for(rint i=1;i<=n;++i){
op[i]=read();x[i]=read();
if(op[i]==1) v[++N]=x[i];//把要插入线段树中的离散化，其它数没有必要
}
sort(v+1,v+1+N);
N=unique(v+1,v+1+N)-v-1;
for(rint i=1;i<=n;++i){
rint tmp=x[i];
if(op[i]!=4) x[i]=lower_bound(v+1,v+1+N,x[i])-v;//这里要把除了查询排名的都离散化
switch(op[i]){
case 1: Ins(1,1,N,x[i],1);break;
case 2: Ins(1,1,N,x[i],-1);break;
case 3: printf("%d\n",query(1,1,N,x[i]-1)+1);break;
case 4: printf("%d\n",v[kth(1,1,N,x[i])]);break;//注意输出原数，下同
case 5: printf("%d\n",v[pre(1,1,N,x[i])]);break;
//找前驱时我们用的是lower_bound，如果树中没有查询的这个数，那么就等价于查最小的比它大的可能在树中的数的前驱
case 6: printf("%d\n",v[suf(1,1,N,(tmp==v[x[i]])?x[i]:(x[i]-1))]);break;
//注意找后继时要特判这个数是否可能在树中，可以手模一下
}
}
return 0;
}