华师一附中OI组

标题: P3369 【模板】普通平衡树 [打印本页]
作者: admin    时间: 2020-3-22 18:54
标题: P3369 【模板】普通平衡树
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    时间: 2020-3-22 18:55
训练简单平衡树的好题，可以用多种树结构做，我先做了有个替罪羊树：
  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;///转移数组

  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;

  28. }

  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. }

  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. }

  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. }

  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. }

  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;

  70.         if( b1|| b2)
  71.         {
  72.                 ita=0;
  73.                 Inorder(rt);
  74.                 rt=build(1,ita);
  75.         }
  76. }

  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. }

  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.         }

  115. }

  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. }

  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. }

  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. }

  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. }

  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    时间: 2020-3-29 10:37
再来一个 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. }

  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. }

  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. }

  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. }


  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.                                                 }

  87.                                 }
  88.                 }
  89. }

  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. }

  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. }

  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. }

  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. }


  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. }

  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. }

  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. */
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2