用途
平衡树(可实现区间翻转)
原理
和treap一样，中序遍历表示权值的顺序，并且每个点有一个随机的附加值，形成一个堆来保证复杂度
但是不旋转，所有操作通过split和merge实现
分为两种split：按权值和按排名
代码
luogu3369 普通平衡树
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long double ld;
const int maxn=1e5+; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} int N,val[maxn],rdt[maxn],siz[maxn],ch[maxn][],pct,root; inline int newnode(int x){
int p=++pct;
val[p]=x;
rdt[p]=rand()<<|rand();
siz[p]=;
ch[p][]=ch[p][]=;
return p;
} inline void print(int x){
if(!x) return;
print(ch[x][]);
printf("##%d %d %d %d %d %d\n",x,val[x],rdt[x],siz[x],ch[x][],ch[x][]);
print(ch[x][]);
} inline void update(int x){siz[x]=+siz[ch[x][]]+siz[ch[x][]];} inline void splitbyrnk(int x,int &l,int &r,int k){
if(!k) l=,r=x;
else if(k==siz[x]) l=x,r=;
else if(k<=siz[ch[x][]]) r=x,splitbyrnk(ch[x][],l,ch[x][],k),update(x);
else l=x,splitbyrnk(ch[x][],ch[x][],r,k-siz[ch[x][]]-),update(x);
} inline void splitbyval(int x,int &l,int &r,int k){ //等于的归右面
if(!x) l=r=;
else if(k<=val[x]) r=x,splitbyval(ch[x][],l,ch[x][],k),update(x);
else l=x,splitbyval(ch[x][],ch[x][],r,k),update(x);
} inline void merge(int &x,int l,int r){
if(!l||!r) x=l+r;
else if(rdt[l]<rdt[r]) x=l,merge(ch[x][],ch[x][],r),update(x);
else x=r,merge(ch[x][],l,ch[x][]),update(x);
} inline void insert(int x){
int p=newnode(x);
int l,r;splitbyval(root,l,r,x);
merge(r,p,r);
merge(root,l,r);
} inline void del(int x){
int l,r;splitbyval(root,l,r,x);
int p;splitbyrnk(r,p,r,);
merge(root,l,r);
} inline int getrnk(int x){
int l,r;splitbyval(root,l,r,x);
int re=siz[l];
merge(root,l,r);
return re+;
} inline int getval(int x){
int l,r;splitbyrnk(root,l,r,x-);
int p;splitbyrnk(r,p,r,);
int re=val[p];
merge(r,p,r);merge(root,l,r);
return re;
} inline int getpre(int x){
return getval(getrnk(x)-);
} inline int getnxt(int x){
return getval(getrnk(x+));
} int main(){
//freopen("","r",stdin);
root=newnode(1e9);
N=rd();
for(int i=;i<=N;i++){
int op=rd(),x=rd();
if(op==) insert(x);
else if(op==) del(x);
else if(op==) printf("%d\n",getrnk(x));
else if(op==) printf("%d\n",getval(x));
else if(op==) printf("%d\n",getpre(x));
else printf("%d\n",getnxt(x));
}
return ;
}