终于还是打了个$Treap$，尽管只有$insert$和$remove$，有时间再补其他函数好了
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<cstdlib>
5 #define MAXN 200010
6 using namespace std;
7 struct _TREAP{
8 //堆的性质是根比儿子要优
9 struct treap{
10 int ls,rs;//左右儿子
11 int val,dat;//关键字，稳定形态的权值
12 int cnt,size;//相同值数，子树大小
13 int fat;
14 }a[MAXN];
15 int tot,root;
16 void init(){
17 tot=0,root=0;
18 a[0].fat=a[0].ls=a[0].rs=a[0].val=a[0].dat=a[0].cnt=a[0].size=0;
19 return ;
20 }
21 int New(int val,int dat){
22 a[++tot].val=val;
23 a[tot].dat=dat;
24 a[tot].cnt=a[tot].size=1;
25 a[tot].fat=a[tot].ls=a[tot].rs=0;
26 return tot;
27 }
28 void up(int p){
29 a[p].size=a[a[p].ls].size+a[a[p].rs].size+a[p].cnt;
30 a[a[p].ls].fat=p;a[a[p].rs].fat=p;
31 return ;
32 }
33 void zig(int &p){//右旋，可以理解为把左儿子旋到根，根到了右儿子上
34 int q=a[p].ls;
35 a[p].ls=a[q].rs;a[q].rs=p;p=q;
36 up(a[p].rs);up(p);
37 return ;
38 }
39 void zag(int &p){//左旋，可以理解为把右儿子旋到根，根到了左儿子上
40 int q=a[p].rs;
41 a[p].rs=a[q].ls;a[q].ls=p;p=q;
42 up(a[p].ls);up(p);
43 return ;
44 }
45 void insert(int &p,int val,int dat=rand()){
46 if(!p){
47 p=New(val,dat);
48 return ;
49 }
50 if(val==a[p].val){
51 ++a[p].cnt,up(p);
52 return ;
53 }
54 if(val<a[p].val){
55 insert(a[p].ls,val,dat);
56 if(a[p].dat<a[a[p].ls].dat)zig(p);
57 }
58 else{
59 insert(a[p].rs,val,dat);
60 if(a[p].dat<a[a[p].rs].dat)zag(p);
61 }
62 up(p);
63 return ;
64 }
65 void remove(int &p,int val){
66 if(!p)return ;
67 if(val==a[p].val){
68 if(a[p].cnt>1){
69 --a[p].cnt,up(p);
70 return ;
71 }
72 else if(a[p].ls+a[p].rs){
73 if(!a[p].rs||a[a[p].ls].dat>a[a[p].rs].dat)zig(p),remove(a[p].rs,val);
74 else zag(p),remove(a[p].ls,val);
75 }
76 else p=0;
77 return ;
78 }
79 val<a[p].val?remove(a[p].ls,val):remove(a[p].rs,val);
80 up(p);
81 return ;
82 }
83 int dist;
84 int Get_dist(int p,int val,int lu){
85 if(!p)return 0;
86 if(a[p].val==val)return lu;
87 return Get_dist(a[p].val<val?a[p].rs:a[p].ls,val,lu+1);
88 }
89 void through_all(int p,int x,int y){
90 if(!p)return ;
91 if(a[p].val>x&&a[p].val>y)through_all(a[p].ls,x,y);
92 else if(a[p].val<x&&a[p].val<y)through_all(a[p].rs,x,y);
93 else dist=Get_dist(p,x,0)+Get_dist(p,y,0);
94 return ;
95 }
96 int LCA(int x,int y){
97 dist=0;
98 through_all(root,x,y);
99 return dist;
100 }
101 void pt(){
102 cout<<endl<<"H---------------H"<<endl;
103 for(int i=1;i<=tot;++i){
104 cout<<"YY "<<a[i].val<<" "<<a[i].dat<<endl;
105 cout<<a[i].ls<<" "<<a[i].rs<<" "<<a[i].fat<<endl;
106 }
107 cout<<"E---------------E"<<endl<<endl;
108 return ;
109 }
110 }T;
111 int n;
112 int main(){
113 //freopen("da.in","r",stdin);
114 T.init();
115 scanf("%d",&n);
116 int opt,a,b;
117 while(n--){
118 scanf("%d",&opt);
119 switch(opt){
120 case 0:{
121 scanf("%d%d",&a,&b),T.insert(T.root,a,b);
122 break;
123 }
124 case 1:{
125 scanf("%d",&a),T.remove(T.root,a);
126 break;
127 }
128 case 2:{
129 scanf("%d%d",&a,&b);
130 printf("%d\n",T.LCA(a,b));
131 break;
132 }
133 }
134 }
135 return 0;
136 }
View Code
基本思想：
为了保持$BST$的深度，对每个节点附上一个$dat$，一般是$rand()$，然后根据这个值来进行左右旋使之结构更优，比$splay$码量小，好理解。估计以后基本平衡树操作都会打$Treap$了吧。