[关闭]
@zzzc18 2017-10-23T10:04:24.000000Z 字数 1915 阅读 540

非旋转式Treap FHQ_Treap

模板库 Treap


%%%%%%% Kirin %%%%%%%

[洛谷]普通平衡树

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<cstdlib>
  5. using namespace std;
  6. int n;
  7. const int MAXN = 100000+9;
  8. struct T{
  9. int val,RD,sz,ls,rs;
  10. }tree[MAXN];
  11. int root;
  12. struct PAIR{
  13. int first,second;
  14. PAIR(){first=second=0;}
  15. };
  16. void update(int x){
  17. tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+1;
  18. }
  19. int New_Node(int x){//woooooooooooooooooooooooooooooo
  20. static int cnt=0;
  21. tree[++cnt].val=x;
  22. tree[cnt].sz=1;
  23. tree[cnt].RD=rand();
  24. return cnt;
  25. }
  26. PAIR split(int x,int val){
  27. PAIR re;
  28. if(x==0){
  29. return re;
  30. }
  31. if(val>=tree[x].val){
  32. re=split(tree[x].rs,val);
  33. tree[x].rs=re.first;
  34. re.first=x;
  35. update(x);
  36. }
  37. else{
  38. re=split(tree[x].ls,val);
  39. tree[x].ls=re.second;
  40. re.second=x;
  41. update(x);
  42. }
  43. return re;
  44. }
  45. int merge(int u,int v){
  46. if(u==0 || v==0){
  47. return u+v;
  48. }
  49. if(tree[u].RD<tree[v].RD){
  50. tree[u].rs=merge(tree[u].rs,v);
  51. update(u);
  52. return u;
  53. }
  54. else{
  55. tree[v].ls=merge(u,tree[v].ls);
  56. update(v);
  57. return v;
  58. }
  59. }
  60. void insert(int val){
  61. PAIR rt=split(root,val);
  62. root=merge(rt.first,merge(New_Node(val),rt.second));
  63. }
  64. void del(int val){
  65. PAIR lrt=split(root,val-1);
  66. PAIR rrt=split(lrt.second,val);
  67. rrt.first=merge(tree[rrt.first].ls,tree[rrt.first].rs);
  68. root=merge(lrt.first,merge(rrt.first,rrt.second));
  69. }
  70. int n2r(int val){
  71. PAIR rt=split(root,val-1);
  72. int re=tree[rt.first].sz+1;
  73. root=merge(rt.first,rt.second);
  74. return re;
  75. }
  76. int r2n(int x,int val){
  77. while(true){
  78. if(tree[tree[x].ls].sz>=val){
  79. x=tree[x].ls;
  80. }
  81. else if(tree[tree[x].ls].sz+1<val){
  82. val-=tree[tree[x].ls].sz+1;
  83. x=tree[x].rs;
  84. }
  85. else{
  86. return tree[x].val;
  87. }
  88. }
  89. }
  90. int pred(int val){
  91. PAIR rt=split(root,val-1);
  92. int re=r2n(rt.first,tree[rt.first].sz);
  93. root=merge(rt.first,rt.second);
  94. return re;
  95. }
  96. int succ(int val){
  97. PAIR rt=split(root,val);
  98. int re=r2n(rt.second,1);
  99. root=merge(rt.first,rt.second);
  100. return re;
  101. }
  102. int main(){
  103. scanf("%d",&n);
  104. int i;
  105. for(i=1;i<=n;i++){
  106. int opt,x;
  107. scanf("%d%d",&opt,&x);
  108. if(opt==1)insert(x);
  109. if(opt==2)del(x);
  110. if(opt==3){printf("%d\n",n2r(x));}
  111. if(opt==4){printf("%d\n",r2n(root,x));}
  112. if(opt==5){printf("%d\n",pred(x));}
  113. if(opt==6){printf("%d\n",succ(x));}
  114. }
  115. return 0;
  116. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注