用途

平衡树(可实现区间翻转)

原理

和treap一样，中序遍历表示权值的顺序，并且每个点有一个随机的附加值，形成一个堆来保证复杂度

但是不旋转，所有操作通过split和merge实现

分为两种split：按权值和按排名

代码

luogu3369 普通平衡树

  1 #include<bits/stdc++.h>
  2 #define pa pair<int,int>
  3 #define CLR(a,x) memset(a,x,sizeof(a))
  4 #define MP make_pair
  5 #define fi first
  6 #define se second
  7 using namespace std;
  8 typedef long long ll;
  9 typedef unsigned long long ull;
 10 typedef unsigned int ui;
 11 typedef long double ld;
 12 const int maxn=1e5+10;
 13 
 14 inline char gc(){
 15     return getchar();
 16     static const int maxs=1<<16;static char buf[maxs],*p1=buf,*p2=buf;
 17     return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++;
 18 }
 19 inline ll rd(){
 20     ll x=0;char c=gc();bool neg=0;
 21     while(c<'0'||c>'9'){if(c=='-') neg=1;c=gc();}
 22     while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=gc();
 23     return neg?(~x+1):x;
 24 }
 25 
 26 int N,val[maxn],rdt[maxn],siz[maxn],ch[maxn][2],pct,root;
 27 
 28 inline int newnode(int x){
 29     int p=++pct;
 30     val[p]=x;
 31     rdt[p]=rand()<<15|rand();
 32     siz[p]=1;
 33     ch[p][0]=ch[p][1]=0;
 34     return p;
 35 }
 36 
 37 inline void print(int x){
 38     if(!x) return;
 39     print(ch[x][0]);
 40     printf("##%d %d %d %d %d %d\n",x,val[x],rdt[x],siz[x],ch[x][0],ch[x][1]);
 41     print(ch[x][1]);
 42 }
 43 
 44 inline void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
 45 
 46 inline void splitbyrnk(int x,int &l,int &r,int k){
 47     if(!k) l=0,r=x;
 48     else if(k==siz[x]) l=x,r=0;
 49     else if(k<=siz[ch[x][0]]) r=x,splitbyrnk(ch[x][0],l,ch[x][0],k),update(x);
 50     else l=x,splitbyrnk(ch[x][1],ch[x][1],r,k-siz[ch[x][0]]-1),update(x);
 51 }
 52 
 53 inline void splitbyval(int x,int &l,int &r,int k){ //等于的归右面
 54     if(!x) l=r=0;
 55     else if(k<=val[x]) r=x,splitbyval(ch[x][0],l,ch[x][0],k),update(x);
 56     else l=x,splitbyval(ch[x][1],ch[x][1],r,k),update(x);
 57 }
 58 
 59 inline void merge(int &x,int l,int r){
 60     if(!l||!r) x=l+r;
 61     else if(rdt[l]<rdt[r]) x=l,merge(ch[x][1],ch[x][1],r),update(x);
 62     else x=r,merge(ch[x][0],l,ch[x][0]),update(x);
 63 }
 64 
 65 inline void insert(int x){
 66     int p=newnode(x);
 67     int l,r;splitbyval(root,l,r,x);
 68     merge(r,p,r);
 69     merge(root,l,r);
 70 }
 71 
 72 inline void del(int x){
 73     int l,r;splitbyval(root,l,r,x);
 74     int p;splitbyrnk(r,p,r,1);
 75     merge(root,l,r);
 76 }
 77 
 78 inline int getrnk(int x){
 79     int l,r;splitbyval(root,l,r,x);
 80     int re=siz[l];
 81     merge(root,l,r);
 82     return re+1;
 83 }
 84 
 85 inline int getval(int x){
 86     int l,r;splitbyrnk(root,l,r,x-1);
 87     int p;splitbyrnk(r,p,r,1);
 88     int re=val[p];
 89     merge(r,p,r);merge(root,l,r);
 90     return re;
 91 }
 92 
 93 inline int getpre(int x){
 94     return getval(getrnk(x)-1);
 95 }
 96 
 97 inline int getnxt(int x){
 98     return getval(getrnk(x+1));
 99 }
100 
101 int main(){
102     //freopen("","r",stdin);
103     root=newnode(1e9);
104     N=rd();
105     for(int i=1;i<=N;i++){
106         int op=rd(),x=rd();
107         if(op==1) insert(x);
108         else if(op==2) del(x);
109         else if(op==3) printf("%d\n",getrnk(x));
110         else if(op==4) printf("%d\n",getval(x));
111         else if(op==5) printf("%d\n",getpre(x));
112         else printf("%d\n",getnxt(x));
113     }
114     return 0;
115 }