P3369 【模板】普通平衡树

admin

https://www.luogu.com.cn/problem/P3369


题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 x 数
删除 x 数(若有多个相同的数，因只删除一个)
查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )
查询排名为 x 的数
求 x 的前驱(前驱定义为小于 x，且最大的数)
求 x 的后继(后继定义为大于 x，且最小的数)
输入格式
第一行为 n，表示操作的个数,下面 n 行每行有两个数opt 和 xx，opt 表示操作的序号(1≤opt≤6 )

输出格式
对于操作 3,4,5,6 每行输出一个数，表示对应答案

输入输出样例
输入 #1复制
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出 #1复制
106465
84185
492737
说明/提示
【数据范围】
对于 100% 的数据，1≤n≤10^5∣x∣≤10^7。

admin

训练简单平衡树的好题，可以用多种树结构做，我先做了有个替罪羊树：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int N = 1001005;
   
4. const float p=0.75;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int ls,rs,sz;  ///lsrs左右儿子  sz本子树下所有节点个数
   
9. } a[N];
   
10. int ta[N],ita;///转移数组
    
11. 
    
12. int n, tot, rt;
    
13. void ArrayPr()
    
14. {
    
15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
16.         cout<<endl;
    
17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
18.         cout<<endl;
    
19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
20.         cout<<endl;
    
21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].ls;
    
22.         cout<<endl;
    
23.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rs;
    
24.         cout<<endl;
    
25.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
26.         cout<<endl;
    
27. 
    
28. }
    
29. 
    
30. void BSTPr(int rt) ///中序输出以rt为根的BST
    
31. {
    
32.         if (a[rt].ls>0)  BSTPr(a[rt].ls);
    
33.         cout<<a[rt].val<<' '; /// 也可以加上cnt
    
34.         if (a[rt].rs>0)  BSTPr(a[rt].rs);
    
35. }
    
36. 
    
37. void pushup(int rt)
    
38. {
    
39.         int l=a[rt].ls, r=a[rt].rs;
    
40.         a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
    
41. }
    
42. 
    
43. int build(int l, int r)//l-r重新建树
    
44. {
    
45.         if(l>r) return 0;
    
46.         int m=(l+r)/2; ///根结点是最中间的那个
    
47.         a[ta[m]].ls=build(l,m-1);
    
48.         a[ta[m]].rs=build(m+1,r);
    
49.         pushup(ta[m]);
    
50.         return ta[m];
    
51. }
    
52. 
    
53. void Inorder(int rt)//倒到数组
    
54. {
    
55.         if(rt>0)
    
56.         {
    
57.                 Inorder(a[rt].ls);
    
58.                 ta[++ita]=rt;
    
59.                 Inorder(a[rt].rs);
    
60.         }
    
61. }
    
62. 
    
63. void RB(int &rt)  ///重建rt
    
64. {
    
65.         if(rt==0) return;
    
66.         float t=a[rt].sz*p; ///左右儿子不能大于rt的0,75
    
67.         bool b1=a[a[rt].ls].sz>t;
    
68.         bool b2=a[a[rt].rs].sz>t;
    
69. 
    
70.         if( b1|| b2)
    
71.         {
    
72.                 ita=0;
    
73.                 Inorder(rt);
    
74.                 rt=build(1,ita);
    
75.         }
    
76. }
    
77. 
    
78. void Ins(int &rt, int x)
    
79. {
    
80.         if(rt==0)
    
81.         {
    
82.                 rt=++tot;
    
83.                 a[rt].val=x;
    
84.                 a[rt].sz=a[rt].cnt = 1;
    
85.         }
    
86.         else
    
87.         {
    
88.                 RB(rt); /// 比原版多一句调整
    
89.                 if(a[rt].val==x) a[rt].cnt ++,a[rt].sz++;
    
90.                 else
    
91.                 {
    
92.                         if(a[rt].val<x) Ins(a[rt].rs, x);
    
93.                         else if(a[rt].val>x) Ins(a[rt].ls, x);
    
94.                         pushup(rt); /// 比原版多一句调整  线段树相似
    
95.                 }
    
96.         }
    
97. }
    
98. 
    
99. int DelMin(int &rt)  ///原版不变
    
100. {
     
101.         int t;
     
102.         if(a[rt].ls==0)///没有左儿子 那就是它
     
103.         {
     
104.                 t=rt;
     
105.                 rt=a[rt].rs;
     
106.                 return t;
     
107.         }
     
108.         else
     
109.         {
     
110.                 t=DelMin(a[rt].ls); ///递归
     
111.                 pushup(rt);///多了这个调整
     
112.                 return t;
     
113.         }
     
114. 
     
115. }
     
116. 
     
117. void Del(int &rt,int x)
     
118. {
     
119.         if (rt==0) return ;
     
120.         else if(a[rt].val>x)    ///左儿子中去找
     
121.         {
     
122.                 Del(a[rt].ls,x);
     
123.                 pushup(rt);
     
124.         }
     
125.         else if(a[rt].val<x)   ///右儿子中去找
     
126.         {
     
127.                 Del(a[rt].rs,x);
     
128.                 pushup(rt);
     
129.         }
     
130.         else if(a[rt].val==x)
     
131.         {
     
132.                 if(a[rt].cnt>1)a[rt].cnt--,a[rt].sz--;  ///次数>1
     
133.                 else if(a[rt].ls==0)rt=a[rt].rs;
     
134.                 else if(a[rt].rs==0)rt=a[rt].ls;
     
135.                 else
     
136.                 {
     
137.                         int t=DelMin(a[rt].rs);
     
138.                         a[rt].val=a[t].val;
     
139.                         a[rt].cnt=a[t].cnt;
     
140.                         pushup(rt);
     
141.                 }
     
142.         }
     
143. }
     
144. 
     
145. int Rank(int rt, int x) ///在RT子树中比x小的数 +1
     
146. {
     
147.         if(a[rt].val==x) return a[a[rt].ls].sz+1; /// 找到了
     
148.         if(a[rt].val<x) return a[a[rt].ls].sz +a[rt].cnt+ Rank(a[rt].rs,x);///左子树下面的都算
     
149.         if(a[rt].val>x) return Rank(a[rt].ls,x);
     
150. }
     
151. 
     
152. int Getkth(int rt, int x) ///在RT子树中找第k小
     
153. {
     
154.         int l=a[a[rt].ls].sz;  /// RT的左儿子下的个数
     
155.         if(l+1<=x && x<=l+a[rt].cnt) return a[rt].val;
     
156.         if(l+1>x) return Getkth(a[rt].ls, x); ///左儿子里去找
     
157.         if(l+a[rt].cnt<x) return Getkth(a[rt].rs, x-(l+a[rt].cnt));
     
158. }
     
159. 
     
160. int Pre(int rt, int x)
     
161. {
     
162.         int p=rt, ans;
     
163.         while(p>0)
     
164.         {
     
165.                 if(x<=a[p].val) p=a[p].ls;
     
166.                 else
     
167.                 {
     
168.                         ans=p;
     
169.                         p=a[p].rs;
     
170.                 }
     
171.         }
     
172.         return ans;
     
173. }
     
174. int Suc(int rt, int x)
     
175. {
     
176.         int p=rt, ans;
     
177.         while(p>0)
     
178.         {
     
179.                 if(a[p].val<=x) p=a[p].rs;
     
180.                 else
     
181.                 {
     
182.                         ans = p;
     
183.                         p=a[p].ls;
     
184.                 }
     
185.         }
     
186.         return ans;
     
187. }
     
188. 
     
189. int main()
     
190. {
     
191.         cin>>n;
     
192.         while(n--)
     
193.         {
     
194.                 int opt, x;
     
195.                 cin>>opt>>x;
     
196.                 if(opt == 1) Ins(rt, x);
     
197.                 if(opt == 2) Del(rt, x);
     
198.                 if(opt == 3) cout<<Rank(rt, x)<<endl;
     
199.                 if(opt == 4) cout<<Getkth(rt, x)<<endl;
     
200.                 if(opt == 5) cout<<a[Pre(rt, x)].val<<endl;
     
201.                 if(opt == 6) cout<<a[Suc(rt, x)].val<<endl;
     
202.                 ///ArrayPr();
     
203.                 ///BSTPr(rt);
     
204.         }
     
205.         return 0;
     
206. }

复制代码

admin

再来一个 treap

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=9999999;
   
4. const int N=100100;
   
5. struct node
   
6. {
   
7.         int val,cnt;
   
8.         int ls,rs,sz,rd;  ///lsrs左右儿子  sz本子树下所有节点个数  rd随机值
   
9. } a[N];
   
10. int n, tot, rt;
    
11. void ArrayPr()   /// 调试监视使用
    
12. {
    
13.         cout<<endl<<"  i ";
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
15.         cout<<endl<<"val ";
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
17.         cout<<endl<<"cnt ";
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
19.         cout<<endl<<" ls ";
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].ls;
    
21.         cout<<endl<<" rs ";
    
22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rs;
    
23.         cout<<endl<<" sz ";
    
24.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
    
25.         cout<<endl<<" rd ";
    
26.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rd;
    
27.         cout<<endl;
    
28. }
    
29. 
    
30. void BSTPr(int rt)   ///中序输出以rt为根的BST
    
31. {
    
32.         if (a[rt].ls>0)  BSTPr(a[rt].ls);
    
33.         cout<<a[rt].val<<' '; /// 也可以加上cnt
    
34.         if (a[rt].rs>0)  BSTPr(a[rt].rs);
    
35. }
    
36. 
    
37. void pushup(int rt)   ///类似线段树网上调整
    
38. {
    
39.         int l=a[rt].ls, r=a[rt].rs;
    
40.         a[rt].sz=a[l].sz+a[r].sz+a[rt].cnt;
    
41. }
    
42. 
    
43. void RR(int &rt) /// 把x的左儿子旋上来当根
    
44. {
    
45.         int l=a[rt].ls;
    
46.         a[rt].ls=a[l].rs;///左儿子的右儿子变成了我的左儿子
    
47.         a[l].rs=rt;///自己变成了左儿子的右儿子
    
48.         pushup(rt),        pushup(l),rt=l;///挂上
    
49. }
    
50. void LR(int &rt)/// 把x的右儿子旋上来当根
    
51. {
    
52.         int r=a[rt].rs;
    
53.         a[rt].rs=a[r].ls;///右儿子的左儿子变成了我的右儿子
    
54.         a[r].ls=rt;///自己变成了右儿子的左儿子
    
55.         pushup(rt),pushup(r),rt=r;///挂上
    
56. }
    
57. 
    
58. 
    
59. void Ins(int &rt, int x)   /// 在rt字数中插入x
    
60. {
    
61.         if(rt==0)   ///空树就新建
    
62.                 {
    
63.                         rt=++tot;
    
64.                         a[rt].val=x;
    
65.                         a[rt].sz=a[rt].cnt=1;
    
66.                         a[rt].rd=rand();
    
67.                 }
    
68.         else
    
69.                 {
    
70.                         a[rt].sz++;
    
71.                         if(a[rt].val==x) a[rt].cnt++;
    
72.                         else
    
73.                                 {
    
74.                                         if(a[rt].val<x)
    
75.                                                 {
    
76.                                                         ///cout<<'R';
    
77.                                                         Ins(a[rt].rs,x);
    
78.                                                         if(a[rt].rd>a[a[rt].rs].rd) LR(rt);
    
79.                                                 }
    
80.                                         else if(a[rt].val>x)
    
81.                                                 {
    
82.                                                         ///cout<<'L';
    
83.                                                         Ins(a[rt].ls, x);
    
84.                                                         if(a[rt].rd>a[a[rt].ls].rd) RR(rt);
    
85.                                                 }
    
86. 
    
87.                                 }
    
88.                 }
    
89. }
    
90. 
    
91. void Del(int &rt,int x)
    
92. {
    
93.         if(rt>0)
    
94.                 if(a[rt].val==x)
    
95.                         {
    
96.                                 if(a[rt].cnt>1)        a[rt].cnt--, a[rt].sz--;    //有相同的就直接cnt--
    
97.                                 else
    
98.                                         {
    
99.                                                 if (a[rt].ls==0) rt=a[rt].rs;
    
100.                                                 else if (a[rt].rs==0) rt=a[rt].ls;
     
101.                                                 else
     
102.                                                         {
     
103.                                                                 if (a[a[rt].ls].rd>a[a[rt].rs].rd) RR(rt);
     
104.                                                                 else LR(rt);
     
105.                                                                 Del(rt,x);
     
106.                                                         }
     
107.                                         }
     
108.                         }
     
109.                 else
     
110.                         {
     
111.                                 a[rt].sz--;
     
112.                                 if (a[rt].val<x) Del(a[rt].rs, x);
     
113.                                 else Del(a[rt].ls, x);
     
114.                         }
     
115. }
     
116. 
     
117. int Rank(int rt, int x)   ///在RT子树中比x小的数 +1
     
118. {
     
119.         if(a[rt].val==x) return a[a[rt].ls].sz+1; /// 找到了
     
120.         if(a[rt].val<x) return a[a[rt].ls].sz +a[rt].cnt+ Rank(a[rt].rs,x);///左子树下面的都算
     
121.         if(a[rt].val>x) return Rank(a[rt].ls,x);
     
122. }
     
123. 
     
124. int Getkth(int rt, int k)   ///在RT子树中找第k小
     
125. {
     
126.         int l=a[a[rt].ls].sz;  /// RT的左儿子下的个数
     
127.         if(l+1<=k && k<=l+a[rt].cnt) return a[rt].val;
     
128.         if(l+1>k) return Getkth(a[rt].ls, k); ///左儿子里去找
     
129.         if(l+a[rt].cnt<k) return Getkth(a[rt].rs, k-(l+a[rt].cnt));///右儿子里去找
     
130. }
     
131. 
     
132. int Pre(int rt, int x)   ///小于x的最大数 这里好像有问题
     
133. {
     
134.         if(rt==0) return 0;
     
135.         if(a[rt].val>=x) return Pre(a[rt].ls,x);//递归查找左子树
     
136.         else
     
137.                 {
     
138.                         int t=Pre(a[rt].rs,x);
     
139.                         if (a[t].val<a[rt].val) return rt;//找右子树中是否存在前驱
     
140.                         else return t;
     
141.                 }
     
142. }
     
143. 
     
144. 
     
145. int Suc(int rt, int x)  ///大于x的最小
     
146. {
     
147.         int p=rt, ans;
     
148.         while(p>0)
     
149.                 {
     
150.                         if(a[p].val<=x) p=a[p].rs;
     
151.                         else
     
152.                                 {
     
153.                                         ans=p;
     
154.                                         p=a[p].ls;
     
155.                                 }
     
156.                 }
     
157.         return ans;
     
158. }
     
159. 
     
160. int main()
     
161. {
     
162.         cin>>n;
     
163.         while(n--)
     
164.                 {
     
165.                         int opt, x;
     
166.                         cin>>opt>>x;
     
167.                         if(opt==1) Ins(rt, x);
     
168.                         if(opt==2) Del(rt, x);
     
169.                         if(opt==3) cout<<Rank(rt, x)<<endl;
     
170.                         if(opt==4) cout<<Getkth(rt, x)<<endl;
     
171.                         if(opt==5)
     
172.                                 {
     
173.                                         a[0].val=-inf;
     
174.                                         cout<<a[Pre(rt, x)].val<<endl;
     
175.                                 }
     
176.                         if(opt==6) cout<<a[Suc(rt, x)].val<<endl;
     
177.                         ///ArrayPr();
     
178.                         ///BSTPr(rt);
     
179.                 }
     
180.         return 0;
     
181. }
     
182. 
     
183. /*
     
184. 10
     
185. 1 1
     
186. 1 2
     
187. 1 5
     
188. 1 8
     
189. 1 9
     
190. 1 7
     
191. 1 6
     
192. 1 1
     
193. 1 2
     
194. 1 9
     
195. */

复制代码