[关闭]
@zzzc18 2017-06-18T07:42:03.000000Z 字数 4532 阅读 606

P3369

洛谷 Treap


Treap其实就是tree+heap
利用随机数给么个节点加上第二个值以实现更稳定的平衡

和Splay类似,都要旋转,不过这个是按堆的性质旋转,好写

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #define MAXN 1000009
  4. using namespace std;
  5. struct T{
  6. int ls,rs,rd,sz,num,val;
  7. }tree[MAXN];
  8. int root,size,ans;
  9. int m;
  10. void update(int x){
  11. tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
  12. }
  13. void rotate_l(int &k){
  14. int y=tree[k].rs;
  15. tree[k].rs=tree[y].ls;
  16. tree[y].ls=k;
  17. tree[y].sz=tree[k].sz;
  18. update(k);
  19. k=y;
  20. }
  21. void rotate_r(int &k){
  22. int y=tree[k].ls;
  23. tree[k].ls=tree[y].rs;
  24. tree[y].rs=k;
  25. tree[y].sz=tree[k].sz;
  26. update(k);
  27. k=y;
  28. }
  29. void insert(int &k,int v){
  30. if(k==0){
  31. size++;k=size;tree[k].val=v;
  32. tree[k].sz=tree[k].num=1;tree[k].rd=rand();
  33. return;
  34. }
  35. tree[k].sz++;
  36. if(tree[k].val==v){
  37. tree[k].num++;
  38. }
  39. else if(v>tree[k].val){
  40. insert(tree[k].rs,v);
  41. if(tree[tree[k].rs].rd<tree[k].rd)rotate_l(k);
  42. }
  43. else{
  44. insert(tree[k].ls,v);
  45. if(tree[tree[k].ls].rd<tree[k].rd)rotate_r(k);
  46. }
  47. }
  48. void del(int &k,int v){
  49. if(k==0)return;
  50. if(tree[k].val==v){
  51. if(tree[k].num>1){
  52. tree[k].sz--;tree[k].num--;
  53. return;
  54. }
  55. if(tree[k].ls==0 || tree[k].rs==0)k=tree[k].ls+tree[k].rs;
  56. else if(tree[tree[k].ls].rd<tree[tree[k].rs].rd){
  57. rotate_r(k);
  58. del(k,v);
  59. }
  60. else{
  61. rotate_l(k);
  62. del(k,v);
  63. }
  64. }
  65. else if(tree[k].val<v){
  66. tree[k].sz--;
  67. del(tree[k].rs,v);
  68. }
  69. else{
  70. tree[k].sz--;
  71. del(tree[k].ls,v);
  72. }
  73. }
  74. int atrank(const int &k,int x){
  75. if(k==0)return 0;
  76. if(tree[k].val==x)
  77. return tree[tree[k].ls].sz+1;
  78. else if(tree[k].val<x)
  79. return tree[tree[k].ls].sz+tree[k].num+atrank(tree[k].rs,x);
  80. else
  81. return atrank(tree[k].ls,x);
  82. }
  83. int rerank(const int &k,int x){
  84. if(k==0) return 0;
  85. if(x<=tree[tree[k].ls].sz) return rerank(tree[k].ls,x);
  86. else if(x>tree[tree[k].ls].sz+tree[k].num)return rerank(tree[k].rs,x-tree[k].num-tree[tree[k].ls].sz);
  87. else return tree[k].val;
  88. }
  89. void pred(const int &k,int x){
  90. if(k==0)return;
  91. if(tree[k].val<x){
  92. ans=k;
  93. pred(tree[k].rs,x);
  94. }
  95. else{
  96. pred(tree[k].ls,x);
  97. }
  98. }
  99. void succ(const int &k,int x){
  100. if(k==0)return;
  101. if(tree[k].val>x){
  102. ans=k;
  103. succ(tree[k].ls,x);
  104. }
  105. else
  106. succ(tree[k].rs,x);
  107. }
  108. int main(){
  109. freopen("treap.in","r",stdin);
  110. scanf("%d",&m);
  111. while(m--){
  112. int opt,x;ans=0;
  113. scanf("%d%d",&opt,&x);
  114. if(opt==1) insert(root,x);
  115. if(opt==2) del(root,x);
  116. if(opt==3) printf("%d\n",atrank(root,x));
  117. if(opt==4) printf("%d\n",rerank(root,x));
  118. if(opt==5) {pred(root,x);printf("%d\n",tree[ans].val);}
  119. if(opt==6) {succ(root,x);printf("%d\n",tree[ans].val);}
  120. }
  121. return 0;
  122. }

注释版

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. using namespace std;
  5. struct TREAP{
  6. int l,r,val,sz,recy,rd;
  7. //sz表示树的节点数,recy记录自己被重复了几次
  8. //rd表示该节点的优先级
  9. }t[1000000];
  10. int m,size,root;
  11. void update(int k){
  12. t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].recy;
  13. //更新维护
  14. }
  15. void left_rotate(int &k){
  16. int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
  17. t[y].sz=t[k].sz;update(k);k=y;
  18. //左旋,至于这里的k=y,由于下面的递归调用,
  19. //它会一直迭代,所以无需担心会有什么错误
  20. }
  21. void right_rotate(int &k){
  22. int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
  23. t[y].sz=t[k].sz;update(k);k=y;
  24. //右旋
  25. }
  26. //以下函数的调用中(int k)表示在根为k的子树中
  27. void insert(int &k,int x){//插入操作
  28. if (k==0){//无节点时特判,
  29. //或是递归的边界,即插入叶节点
  30. ++size;k=size;t[k].sz=t[k].recy=1;
  31. t[k].val=x;t[k].rd=rand();return ;
  32. //rand()生成随机的优先级,保证了期望复杂度
  33. }
  34. ++t[k].sz;//每次向下找同时增加该节点1个节点数
  35. if (t[k].val==x) ++t[k].recy;
  36. //如果是相同数字,只需++recy即可
  37. else if (x>t[k].val){
  38. insert(t[k].r,x);
  39. if (t[t[k].r].rd<t[k].rd) left_rotate(k);
  40. //插入后如果违反堆性质,就进行上浮
  41. }else{
  42. insert(t[k].l,x);
  43. if (t[t[k].l].rd<t[k].rd) right_rotate(k);
  44. }
  45. }
  46. void del(int &k,int x){
  47. if (k==0) return ;//无节点就跳出
  48. if (t[k].val==x){
  49. if (t[k].recy>1){
  50. --t[k].recy;--t[k].sz;return ;
  51. //如果重复了,只需--recy即可
  52. }
  53. if (t[k].l*t[k].r==0) k=t[k].l+t[k].r;
  54. //如果左右儿子有为空的情况
  55. //或将其变为其儿子节点,或将其删除
  56. else if (t[t[k].l].rd<t[t[k].r].rd)
  57. right_rotate(k),del(k,x);
  58. //如果其左右儿子都有,选择优先级较大的,
  59. //保持以后的堆性质,同时将k节点下沉
  60. else left_rotate(k),del(k,x);
  61. }
  62. else if (x>t[k].val)
  63. --t[k].sz,del(t[k].r,x);
  64. //如果关键值不同,继续向下找
  65. else --t[k].sz,del(t[k].l,x);
  66. }
  67. int atrank(int k,int x){//寻找值为x的数的排名
  68. if (k==0) return 0;
  69. if (t[k].val==x) return t[t[k].l].sz+1;
  70. //如果找的关键字,根据BST的性质,
  71. //则其排名为左子树的大小+1
  72. else if (x>t[k].val)
  73. return t[t[k].l].sz+t[k].recy+atrank(t[k].r,x);
  74. //加上前面所有比它小的数,在右子树中找
  75. else return atrank(t[k].l,x);
  76. //如果在左子树中找的话就不用加了
  77. }
  78. int rerank(int k,int x){//寻找排名为x的数值
  79. if (k==0) return 0;
  80. if (x<=t[t[k].l].sz) return rerank(t[k].l,x);
  81. //如果x小于了左子树的大小,那解一定在左子树中
  82. else if (x>t[t[k].l].sz+t[k].recy)
  83. return rerank(t[k].r,x-t[k].recy-t[t[k].l].sz);
  84. //如果x大于的左子树的大小+k的重复次数,
  85. //那就在右子树中找
  86. else return t[k].val;
  87. //否则就是找到解了(包含了重复数字中)
  88. }
  89. void pred(int k,int x){//找前缀
  90. if (k==0) return ;
  91. if (t[k].val<x){
  92. ans=k;pred(t[k].r,x);
  93. //找到了更优的解,就替换之
  94. //而且在其右子树中不可能再有更优的了
  95. //故向其左子树中找
  96. }else pred(t[k].l,x);
  97. //否则就往右子树中找
  98. }
  99. void succ(int k,int x){//找后缀
  100. if (k==0) return ;
  101. if (t[k].val>x){
  102. ans=k;succ(t[k].l,x);
  103. }else succ(t[k].r,x);
  104. }
  105. int main(){
  106. int f,x;
  107. scanf("%d",&m);
  108. for (int i=1;i<=m;++i){
  109. scanf("%d%d",&f,&x);ans=0;
  110. if (f==1) insert(root,x);
  111. if (f==2) del(root,x);
  112. if (f==3) printf("%d\n",atrank(root,x));
  113. if (f==4) printf("%d\n",rerank(root,x));
  114. if (f==5) {pred(root,x);printf("%d\n",t[ans].val);}
  115. if (f==6) {succ(root,x);printf("%d\n",t[ans].val);}
  116. }
  117. return 0;
  118. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注