[关闭]
@KirinBill 2017-09-18T04:27:43.000000Z 字数 9859 阅读 915

非旋转式Treap学习笔记

学习笔记 数据结构

目录


基础知识

定义


实现

一些约定:记的随机优先级,的权值,等类似。这里的Treap是小根堆


底层函数:

Build

建树。。。

Split

按值的大小或序列顺序将Treap分为两个,返回两个根(即左树的节点值小于等于某个值,或左树节点为维护的序列的前k个)。


功能函数:

Insert

在Treap中插入一个节点。

Delete

在Treap中删除一个节点。

GetRank

查询一个值在Treap中的排名。

KthVal

查询Treap中排名为k的值。

Predecessor

查询一个值在Treap中的前驱。

Successor

查询一个值在Treap中的后继。

Reverse

对于维护序列的Treap来说,将该序列中某一个区间反转一下。


练习

[洛谷 P3369] 普通平衡树

代码:

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <utility>
  4. #define lrt first
  5. #define rrt second
  6. using std::pair;
  7. typedef pair<int,int> dual_rt;
  8. const int MAXN=100005;
  9. struct node{
  10. int ls,rs,val,key,sz;
  11. friend bool operator< (const node &a,const node &b){
  12. return a.val<b.val;
  13. }
  14. };
  15. class FHQ_Treap{
  16. private:
  17. int rt;
  18. node d[MAXN];
  19. void upd(int u){
  20. d[u].sz=d[d[u].ls].sz+d[d[u].rs].sz+1;
  21. }
  22. int new_nd(int val){
  23. static int cnt=0;
  24. d[++cnt].val=val;
  25. d[cnt].key=rand();
  26. d[cnt].sz=1;
  27. return cnt;
  28. }
  29. dual_rt split(int u,int val){
  30. dual_rt ret(0,0);
  31. if(!u) return ret;
  32. if(val<d[u].val){
  33. ret=split(d[u].ls,val);
  34. d[u].ls=ret.rrt;
  35. ret.rrt=u;
  36. }
  37. else{
  38. ret=split(d[u].rs,val);
  39. d[u].rs=ret.lrt;
  40. ret.lrt=u;
  41. }
  42. upd(u);
  43. return ret;
  44. }
  45. int merge(int u,int v){
  46. if(!u) return v;
  47. else if(!v) return u;
  48. if(d[u].key<d[v].key){
  49. d[u].rs=merge(d[u].rs,v);
  50. upd(u);
  51. return u;
  52. }
  53. else{
  54. d[v].ls=merge(u,d[v].ls);
  55. upd(v);
  56. return v;
  57. }
  58. }
  59. int kth_val(int u,int k){
  60. while(true){
  61. if(k<=d[d[u].ls].sz)
  62. u=d[u].ls;
  63. else if(d[d[u].ls].sz+1<k){
  64. k-=d[d[u].ls].sz+1;
  65. u=d[u].rs;
  66. }
  67. else break;
  68. }
  69. return d[u].val;
  70. }
  71. public:
  72. void ist(int val){
  73. dual_rt x=split(rt,val);
  74. rt=merge(merge(x.lrt,new_nd(val)),x.rrt);
  75. }
  76. void del(int val){
  77. dual_rt x=split(rt,val);
  78. dual_rt y=split(x.lrt,val-1);
  79. y.rrt=merge(d[y.rrt].ls,d[y.rrt].rs);
  80. rt=merge(merge(y.lrt,y.rrt),x.rrt);
  81. }
  82. int get_rk(int val){
  83. dual_rt x=split(rt,val-1);
  84. int ret=d[x.lrt].sz+1;
  85. rt=merge(x.lrt,x.rrt);
  86. return ret;
  87. }
  88. int kth_val(int k){return kth_val(rt,k);}
  89. int pred(int val){
  90. dual_rt x=split(rt,val-1);
  91. int ret=kth_val(x.lrt,d[x.lrt].sz);
  92. rt=merge(x.lrt,x.rrt);
  93. return ret;
  94. }
  95. int succ(int val){
  96. dual_rt x=split(rt,val);
  97. int ret=kth_val(x.rrt,1);
  98. rt=merge(x.lrt,x.rrt);
  99. return ret;
  100. }
  101. }T;
  102. int main(){
  103. int n;
  104. scanf("%d",&n);
  105. for(int i=1,opt,x;i<=n;++i){
  106. scanf("%d%d",&opt,&x);
  107. switch(opt){
  108. case 1: T.ist(x); break;
  109. case 2: T.del(x); break;
  110. case 3: printf("%d\n",T.get_rk(x));
  111. break;
  112. case 4: printf("%d\n",T.kth_val(x));
  113. break;
  114. case 5: printf("%d\n",T.pred(x));
  115. break;
  116. default:printf("%d\n",T.succ(x));
  117. }
  118. }
  119. return 0;
  120. }

[洛谷 P3391] 文艺平衡树

代码:

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <stack>
  6. #define lrt first
  7. #define rrt second
  8. using std::swap;
  9. using std::pair;
  10. using std::stack;
  11. typedef pair<int,int> dual_rt;
  12. const int MAXN=100005;
  13. int tmp[MAXN];
  14. struct node{
  15. int s[2],sz,val,key;
  16. bool rev;
  17. };
  18. class seq_Treap{
  19. private:
  20. int rt;
  21. node d[MAXN];
  22. void upd(int u){
  23. d[u].sz=d[d[u].s[0]].sz+d[d[u].s[1]].sz+1;
  24. }
  25. void push_d(int u){
  26. if(d[u].rev){
  27. swap(d[u].s[0],d[u].s[1]);
  28. d[d[u].s[0]].rev^=true;
  29. d[d[u].s[1]].rev^=true;
  30. d[u].rev=false;
  31. }
  32. }
  33. dual_rt split(int u,int k){
  34. dual_rt ret(0,0);
  35. if(!u) return ret;
  36. push_d(u);
  37. if(k<=d[d[u].s[0]].sz){
  38. ret=split(d[u].s[0],k);
  39. d[u].s[0]=ret.rrt;
  40. ret.rrt=u;
  41. }
  42. else{
  43. ret=split(d[u].s[1],k-d[d[u].s[0]].sz-1);
  44. d[u].s[1]=ret.lrt;
  45. ret.lrt=u;
  46. }
  47. upd(u);
  48. return ret;
  49. }
  50. int merge(int u,int v){
  51. if(!u) return v;
  52. push_d(u);
  53. if(!v) return u;
  54. push_d(v);
  55. if(d[u].key<d[v].key){
  56. d[u].s[1]=merge(d[u].s[1],v);
  57. upd(u);
  58. return u;
  59. }
  60. else{
  61. d[v].s[0]=merge(u,d[v].s[0]);
  62. upd(v);
  63. return v;
  64. }
  65. }
  66. void inorder_prt(int u){
  67. push_d(u);
  68. if(d[u].s[0]) inorder_prt(d[u].s[0]);
  69. printf("%d ",d[u].val);
  70. if(d[u].s[1]) inorder_prt(d[u].s[1]);
  71. }
  72. public:
  73. void build(int n,int a[]){
  74. static stack<int> stk;
  75. stk.push(0);
  76. for(int i=1,fa;i<=n;++i){
  77. d[i].val=a[i];
  78. d[i].key=rand();
  79. d[i].sz=1;
  80. while(fa=stk.top(),d[fa].key>d[i].key){
  81. upd(fa);
  82. stk.pop();
  83. }
  84. d[i].s[0]=d[fa].s[1];
  85. d[fa].s[1]=i;
  86. stk.push(i);
  87. }
  88. while(stk.size()>1){
  89. upd(stk.top());
  90. stk.pop();
  91. }
  92. stk.pop();
  93. rt=d[0].s[1];
  94. }
  95. void rvs(int l,int r){
  96. dual_rt x=split(rt,l-1);
  97. dual_rt y=split(x.rrt,r-l+1);
  98. d[y.lrt].rev^=true;
  99. rt=merge(merge(x.lrt,y.lrt),y.rrt);
  100. }
  101. void prt(){inorder_prt(rt);}
  102. }T;
  103. int main(){
  104. int n,m;
  105. scanf("%d%d",&n,&m);
  106. for(int i=1;i<=n;++i)
  107. tmp[i]=i;
  108. T.build(n,tmp);
  109. for(int i=1,l,r;i<=m;++i){
  110. scanf("%d%d",&l,&r);
  111. T.rvs(l,r);
  112. }
  113. T.prt();
  114. return 0;
  115. }

[2017.9.9 NOIP模拟赛] 完整的海报

GJw9a.png

代码:

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. x=0;
  13. int pm=1; char c;
  14. do{c=getchar();}while(!isdigit(c) && c!='-');
  15. c=='-' ? pm=-1:x=c^'0';
  16. while(c=getchar(),isdigit(c))
  17. x=x*10+(c^'0');
  18. x*=pm;
  19. }
  20. template<typename type>
  21. void write(type x,char c=0){
  22. if(x<0) putchar('-'),x=-x;
  23. if(x>9) write(x/10);
  24. putchar(x%10|'0');
  25. if(c) putchar(c);
  26. }
  27. #include <cstdlib>
  28. #include <climits>
  29. const int MAXN=200005;
  30. int n,L,tt;
  31. class FHQ_Treap{
  32. private:
  33. int rt,cnt;
  34. struct dual_rt{int lrt,rrt;};
  35. struct node{int ls,rs,val,key,sz;}d[MAXN];
  36. int new_nd(int val){
  37. d[++cnt].val=val;
  38. d[cnt].key=rand();
  39. d[cnt].sz=1;
  40. return cnt;
  41. }
  42. void upd(int u){
  43. d[u].sz=d[d[u].ls].sz+d[d[u].rs].sz+1;
  44. }
  45. dual_rt split(int u,int val){
  46. dual_rt ret=(dual_rt){0,0};
  47. if(!u) return ret;
  48. if(val<d[u].val){
  49. ret=split(d[u].ls,val);
  50. d[u].ls=ret.rrt;
  51. ret.rrt=u;
  52. }
  53. else{
  54. ret=split(d[u].rs,val);
  55. d[u].rs=ret.lrt;
  56. ret.lrt=u;
  57. }
  58. upd(u);
  59. return ret;
  60. }
  61. int merge(int u,int v){
  62. if(!u) return v;
  63. else if(!v) return u;
  64. if(d[u].key<d[v].key){
  65. d[u].rs=merge(d[u].rs,v);
  66. upd(u);
  67. return u;
  68. }
  69. else{
  70. d[v].ls=merge(u,d[v].ls);
  71. upd(v);
  72. return v;
  73. }
  74. }
  75. int kth_val(int u,int k){
  76. if(!k) return -1;
  77. while(true){
  78. if(k<=d[d[u].ls].sz) u=d[u].ls;
  79. else if(k>d[d[u].ls].sz+1){
  80. k-=d[d[u].ls].sz+1;
  81. u=d[u].rs;
  82. }
  83. else return d[u].val;
  84. }
  85. }
  86. public:
  87. void ist(int val){
  88. dual_rt x=split(rt,val);
  89. rt=merge(merge(x.lrt,new_nd(val)),x.rrt);
  90. }
  91. void del(int lval,int rval){
  92. dual_rt x=split(rt,lval);
  93. dual_rt y=split(x.rrt,rval-1);
  94. rt=merge(x.lrt,y.rrt);
  95. }
  96. int lge_cnt(int val){
  97. dual_rt x=split(rt,val);
  98. int ret=d[x.rrt].sz;
  99. rt=merge(x.lrt,x.rrt);
  100. return ret;
  101. }
  102. int geq_cnt(int val){
  103. dual_rt x=split(rt,val-1);
  104. int ret=d[x.rrt].sz;
  105. rt=merge(x.lrt,x.rrt);
  106. return ret;
  107. }
  108. int pred(int val){
  109. dual_rt x=split(rt,val-1);
  110. int ret=kth_val(x.lrt,d[x.lrt].sz);
  111. rt=merge(x.lrt,x.rrt);
  112. return ret==0 ? INT_MIN:ret;
  113. }
  114. int succ(int val){
  115. dual_rt x=split(rt,val);
  116. int ret=kth_val(x.rrt,1);
  117. rt=merge(x.lrt,x.rrt);
  118. return ret==0 ? INT_MAX:ret;
  119. }
  120. }lp,rp;
  121. inline int add(int l,int r){
  122. static int ret=0;
  123. ret-=rp.geq_cnt(l)-lp.lge_cnt(r);
  124. ++ret;
  125. lp.del(rp.pred(l),r+1);
  126. lp.ist(l);
  127. rp.del(l-1,lp.succ(r));
  128. rp.ist(r);
  129. return ret;
  130. }
  131. int main(){
  132. setIO("poster");
  133. read(L),read(n),read(tt);
  134. if(tt){
  135. for(int i=1,x,y,lastans=0;i<=n;++i){
  136. read(x),read(y);
  137. x^=lastans,y^=lastans;
  138. lastans=add(x,y);
  139. write(lastans,'\n');
  140. }
  141. }
  142. else{
  143. for(int i=1,x,y;i<=n;++i){
  144. read(x),read(y);
  145. write(add(x,y),'\n');
  146. }
  147. }
  148. return 0;
  149. }

应用

作为普通的平衡树

可持久化

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注