wa record

本来按权值分裂AC了qaq

但是做文艺平衡树的时候区间翻转据说一定要按排名

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,sz,val[N],rnd[N],siz[N],ch[N][3];
void update(int v){
	siz[v]=siz[ch[v][0]]+siz[ch[v][1]]+1;
}
int new_node(int v){
	siz[++sz]=1;
	rnd[sz]=rand();
	val[sz]=v;
	return sz;
}
void split(int now,int k,int &x,int &y){
	if(!now) x=y=0;
	else{
		if(siz[ch[now][0]]<k) x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y); 
		else y=now,split(ch[now][0],k,x,ch[now][0]);
		update(now);
	}
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(rnd[x]<rnd[y]){
		ch[x][1]=merge(ch[x][1],y);
		update(x);
		return x;
	} else{
		ch[y][0]=merge(x,ch[y][0]);
		update(y);
		return y;
	}
}
int kth(int now,int k){
	while(1){
		if(k<=siz[ch[now][0]]){
			now=ch[now][0];
		} else if(k==siz[ch[now][0]]+1){
			return now;
		} else {
			k-=siz[ch[now][0]]+1;
			now=ch[now][1];
		}
	}
}
int rk(int now,int v){
	if(!now) return 0;
	if(v<val[now]) return rk(ch[now][0],v);
	else if(v==val[now]) return siz[ch[now][1]]+1;
	else return siz[ch[now][0]]+1+rk(ch[now][1],v);
}
int main(){
	int opt,rt=0,num,x,y,z,tmp;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&opt,&num);
		if(opt==1){//插入x数 
			split(rt,rk(rt,num),x,y);
			rt=merge(merge(x,new_node(num)),y);
		} else if(opt==2) {//删除x数
			split(rt,rk(rt,num),x,z);
			split(x,rk(rt,num-1),x,y);
			rt=merge(merge(x,y),z);
		} else if(opt==3) {//查询x数的排名(排名定义为比当前数小的数的个数+1) 
			printf("%d\n",rk(rt,num));
		} else if(opt==4) {//查询排名为x的数
			printf("%d\n",val[kth(rt,num)]);
		} else if(opt==5) {//求x的前驱(前驱定义为小于x，且最大的数)
			split(rt,rk(rt,num-1),x,y);
			printf("%d\n",val[kth(x,siz[x])]);
			rt=merge(x,y);
		} else if(opt==6) {//求x的后继(后继定义为大于x，且最小的数)
			split(rt,rk(rt,num),x,y);
			printf("%d\n",val[kth(y,1)]);
			rt=merge(x,y);
		}
	}
	return 0;
}