几种常用平衡树的概述（持续更新]

  1 //Author : 15owzLy1
  2 //luogu3369.cpp
  3 //2018 12 05      22:37:51
  4 #include <iostream>
  5 #include <cstdio>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <cstdlib>
  9 #define INF 2100000000
 10 typedef long long ll;
 11 typedef double db;
 12 template<typename T>inline void read(T &_) {
 13     _=0;int __=0;char ___=getchar();
 14     while(___<‘0‘||___>‘9‘)__|=(___==‘-‘),___=getchar();
 15     while(___>=‘0‘&&___<=‘9‘)_=(_<<1)+(_<<3)+(___^48),___=getchar();
 16     _=__?-_:_;
 17 }
 18 
 19 const int N = 100005;
 20 int q,opt,y,res;
 21 
 22 class Treap {
 23 #define t a[p]
 24 #define lson a[a[p].l]
 25 #define rson a[a[p].r]
 26 private :
 27     int tot; 
 28     struct node {
 29         int l,r,val,num,w,size;
 30     }a[N];
 31     inline void push_up(int p) {
 32         t.size=lson.size+rson.size+t.val;
 33     }
 34     inline void zig(int &p) {
 35         int ts=lson.r,tmp=t.l;
 36         lson.size=t.size;
 37         lson.r=p,t.l=ts;
 38         push_up(p);
 39         p=tmp;
 40     }
 41     inline void zag(int &p) {
 42         int ts=rson.l,tmp=t.r;
 43         rson.size=t.size;
 44         rson.l=p,t.r=ts;
 45         push_up(p);
 46         p=tmp;
 47     }
 48     inline void new_node(int &p,int x) {
 49         t=(node){0,0,1,x,rand(),1};
 50     }
 51 public :
 52     int rt;
 53     void debug(int p) {
 54         if(t.l) debug(t.l);
 55         printf("num : %d  p : %dn",t.num,p);
 56         if(t.r) debug(t.r);
 57     }
 58     void insert(int &p,int x) {
 59         if(!p) { p=++tot; new_node(p,x); return ; }
 60         ++t.size;
 61         if(t.num==x) ++t.val;
 62         else if(x<t.num) {
 63             insert(t.l,x);
 64             if(t.w<lson.w) zig(p);
 65         }
 66         else {
 67             insert(t.r,x);
 68             if(t.w<rson.w) zag(p);
 69         }
 70     }
 71     void del(int &p,int x) {
 72         if(t.num==x) {
 73             if(t.val>1) --t.val,--t.size;
 74             else if(t.l==0||t.r==0) p=t.l?t.l:t.r;
 75             else if(lson.w>rson.w) zig(p),del(p,x);
 76             else                   zag(p),x);
 77         }
 78         else if(x<t.num) { --t.size; del(t.l,x); }
 79         else             { --t.size; del(t.r,x); }
 80     }
 81     int query_rank(int p,int x) {
 82         if(x==t.num)     return lson.size+1;
 83         else if(x<t.num) return query_rank(t.l,x);
 84         else             return query_rank(t.r,x)+lson.size+t.val;
 85     }
 86     int query_num(int p,int x) {
 87         if(!p) return 0;
 88         if(lson.size<x&&lson.size+t.val>=x) return t.num;
 89         if(lson.size>=x) return query_num(t.l,x);
 90         return query_num(t.r,x-t.val-lson.size);
 91     }
 92     void query_pre(int p,int x) {
 93         if(!p) return ;
 94         if(x<=t.num) query_pre(t.l,x);
 95         else {
 96             res=t.num;
 97             query_pre(t.r,x);
 98         }
 99     }
100     void query_sub(int p,int x) {
101         if(!p) return ;
102         if(x>=t.num) query_sub(t.r,x);
103         else {
104             res=t.num;
105             query_sub(t.l,x);
106         }
107     }
108 }T;
109 
110 int main() {
111 #ifndef ONLINE_JUDGE
112     freopen("luogu3369.in","r",stdin);
113     freopen("luogu3369.out","w",stdout);
114 #endif
115     srand(20030215);
116     read(q);
117     while(q--) {
118         read(opt),read(y);
119         if(opt==1)        T.insert(T.rt,y);
120         else if(opt==2) T.del(T.rt,y);
121         else if(opt==3) printf("%dn",T.query_rank(T.rt,y));
122         else if(opt==4) printf("%dn",T.query_num(T.rt,y));
123         else if(opt==5) {
124             res=-INF;
125             T.query_pre(T.rt,y);
126             printf("%dn",res);
127         }
128         else {
129             res=INF;
130             T.query_sub(T.rt,y);
131             printf("%dn",res);
132         }
133     }
134     return 0;
135 }

 1 //Author : 15owzLy1
 2 //luogu3391.cpp
 3 //2018 12 11      10:38:52
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <algorithm>
 7 #define INF 2100000000
 8 typedef long long ll;
 9 typedef double db;
10 template<typename T>inline void read(T &_) {
11     _=0;int __=0;char ___=getchar();
12     while(___<‘0‘||___>‘9‘)__|=(___==‘-‘),___=getchar();
13     while(___>=‘0‘&&___<=‘9‘)_=(_<<1)+(_<<3)+(___^48),___=getchar();
14     _=__?-_:_;
15 }
16 
17 const int N = (int)1e5+5;
18 int n,q,y;
19 
20 class Splay {
21 #define lson c[p][0]
22 #define rson c[p][1]
23 private :
24     int c[N][2],fa[N],size[N],num[N],lazy[N];
25     inline void push_up(int p) {
26         size[p]=size[lson]+size[rson]+1;
27     }
28     inline void push_down(int p) {
29         if(lazy[p]) {
30             std::swap(lson,rson);
31             lazy[lson]^=1,lazy[rson]^=1;
32             lazy[p]=0;
33         }
34     }
35     inline void rotate(int x,int &p) {
36         int y=fa[x],z=fa[y],l,r;
37         l=(c[y][1]==x); r=l^1;
38         if(y==p) p=x;
39         else     c[z][c[z][1]==y]=x;
40         fa[c[x][r]]=y,fa[x]=z,fa[y]=x;    
41         c[y][l]=c[x][r],c[x][r]=y;
42         push_up(x),push_up(y);
43     }
44 public :
45     int rt;
46     inline void splay(int x,int &p) {
47         while(x!=p) {
48             int y=fa[x],z=fa[y];
49             if(y!=p) {
50                 if(c[y][0]==x^c[z][0]==y) rotate(x,p);
51                 else rotate(y,p);
52             }
53             rotate(x,p);
54         }
55     }
56     int find(int p,int rank) {
57         push_down(p);
58         if(size[lson]+1==rank)   return p;
59         else if(size[lson]>=rank)return find(lson,rank);
60         else                  return find(rson,rank-size[lson]-1);
61     }
62     inline void reverse(int x,int y) {
63         int l=find(rt,x),r=find(rt,y+2);
64         splay(l,rt),splay(r,c[l][1]);
65         lazy[c[r][0]]^=1;
66     }
67     void build(int l,int r,int father) {
68         if(l>r) return ;
69         int mid=l+r>>1;
70         c[father][mid>=father]=mid;
71         fa[mid]=father; size[mid]=1;
72         if(l==r) return ;
73         build(l,mid-1,mid);
74         build(mid+1,mid);
75         push_up(mid);
76     }
77 }T;
78 
79 int main() {
80 #ifndef ONLINE_JUDGE
81     freopen("luogu3391.in",stdin);
82 #endif
83     read(n),read(q);
84     T.rt=(n+3)>>1; T.build(1,n+2,T.rt);
85     while(q--) {
86         read(x),read(y);
87         T.reverse(x,y);
88     }
89     for(int i=2;i<=n+1;i++)
90         printf("%d ",T.find(T.rt,i)-1);
91     return 0;
92 }

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cstdlib>
  5 
  6 template<typename T>inline void read(T &x) {
  7     x=0;int f=0;char c=getchar();
  8     while(c<‘0‘||c>‘9‘)f|=(c==‘-‘),c=getchar();
  9     while(c>=‘0‘&&c<=‘9‘)x=(x<<1)+(x<<3)+(c^48),c=getchar();
 10     x=f?-x:x;
 11 }
 12 
 13 const int N = (int)1e5+5;
 14 int q,n;
 15 
 16 class Persistence_Treap {
 17 #define t a[p]
 18 #define lson a[a[p].l]
 19 #define rson a[a[p].r]
 20 private :
 21     struct node {
 22         int l,size,w;
 23     }a[N];
 24     inline void push_up(int p) {
 25         t.size=lson.size+rson.size+1;
 26     }
 27     void split(int p,int &x,int &y,int k) {
 28         if(p==0) { x=y=0; return ; }
 29         if(t.num<=k) x=p,split(t.r,t.r,k);
 30         else         y=p,split(t.l,t.l,k);
 31         push_up(p);
 32     }
 33     int merge(int &p,int x,int y) {
 34         if(x==0||y==0) { p=x?x:y; return p; }
 35         if(a[x].w<a[y].w) { p=x; merge(t.r,y); }
 36         else              { p=y; merge(t.l,t.l); }
 37         push_up(p);
 38         return p;
 39     }
 40     inline int new_node(int k) {
 41         a[++tot]=(node){0,k,1,rand()};
 42         return tot;
 43     }
 44 public :
 45     int rt,tot;
 46     void debug(int p) {
 47         if(t.l) debug(t.l);
 48         printf("   %d %d %d %dn",lson.num,rson.num,t.size);
 49         if(t.r) debug(t.r);
 50     }
 51     inline void insert(int k) {
 52         int x=0,y=0,z=new_node(k);
 53         split(rt,k);
 54         merge(rt,merge(x,z),y);
 55     }
 56     inline void remove(int k) {
 57         int x=0,z=0;
 58         split(rt,k);
 59         split(x,z,k-1);
 60         merge(rt,merge(z,a[z].l,a[z].r)),y);
 61     }
 62     inline int find(int k) {
 63         int x=0,y=0,ret;
 64         split(rt,k-1);
 65         ret=a[x].size+1;
 66         merge(rt,y);
 67         return ret;
 68     }
 69     inline int kth(int p,int k) {
 70         while(lson.size+1!=k) {
 71             if(lson.size>=k) p=t.l;
 72             else             k-=lson.size+1,p=t.r;
 73         }
 74         return t.num;
 75     }
 76     inline int query_pre(int k) {
 77         int x=0,ret;
 78         split(rt,k-1);
 79         ret=kth(x,a[x].size);
 80         merge(rt,y);
 81         return ret;
 82     }
 83     inline int query_sub(int k) {
 84         int x=0,ret;
 85         split(rt,k);
 86         ret=kth(y,1);
 87         merge(rt,y);
 88         return ret;
 89     }
 90 }T;
 91 
 92 int main() {
 93 #ifndef ONLINE_JUDGE
 94     freopen("fhq_treap.in",stdin);
 95 #endif
 96     srand(20030215);
 97     read(q);
 98     while(q--) {
 99         read(opt),read(n);
100         switch(opt) {
101             case 1 : T.insert(n);break;
102             case 2 : T.remove(n);break;
103             case 3 : printf("%dn",T.find(n));break;
104             case 4 : printf("%dn",T.kth(T.rt,n));break;
105             case 5 : printf("%dn",T.query_pre(n));break;
106             case 6 : printf("%dn",T.query_sub(n));break;
107         }
108     }
109     return 0;
110 }