不用旋转的treap？——fhq treap

#fhq treap——无旋treap ###●前置知识：[二叉排序树](https://www.luogu.org/blog/ztz11/pinghengshu-bst) [treap](https://blog.csdn.net/simpsonk/article/details/72832959) [了解什么是函数式编程](https://www.sohu.com/a/222320820_355140) ###●本文代码均未经编译，如有错误请指出。 ###●QQ826755370 ##引入 -“平衡树好烦啊，转来转去的，而且treap遇到区间序列问题就gg。” -“有一种不用旋转的treap，叫fhq treap，可以解决区间序列问题。” ##正文 ###约定 我们做出以下约定： ```cpp int ch[MAXN][3];//0 左孩子，1右孩子 int val[MAXN];//每个点的权值 int rnd[MAXN];//每个点的随机权值 int size[MAXN];//以每个点为根的树的大小 ``` ###分裂  分裂有两种，一种是权值分裂，一种是排名分裂。我们先讲权值分裂。如图，当我们遍历到一个节点时，如果它的权值小于k，那么它的左子树会被分到左边的树里，然后我们遍历它的右儿子，如果大于k，则把它的右子树分到右边的树里。如果到达递归边界now==0怎么办呢？这里会有两种情况： 1.root=0（即第一次split），很明显要给x和y初始化，即x=y=0。 2.split到了叶子节点，此时无法继续split了，只能返回。此时的x=y=0没什么用，因为x和y会在回溯的时候通过地址符号改变。 代码： ```cpp void split(int now,int k,int &x,int &y) { if(!now) x=y=0; else if(val[now]<=k) { x=now; split(ch[now][1],k,ch[now][1],y); } else { y=now; split(ch[now][0],k,x,ch[now][0]); } update(now);//update(i)为更新size[i]大小的函数 } ``` 排名分裂与权值分裂类似，即将前k个放在一颗树里，其余的放在另一棵树里。代码： ```cpp void split(int now,int k,int &x,int &y) { if(!now) x=y=0; else { if(k<=siz[ch[now][0]]) { y=now; split(ch[now][0],k,x,ch[now][0]); } else { x=now; split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y); } update(now); } } ``` ###合并  如图，我们假设第一棵树的权值小于第二棵树的权值，那么我们就比较它们的随机权值。如果rnd[l]<rnd[r]，我们就保留它的左子树，另一棵树作为它的右子树；如果rnd[l]>=rnd[r]，那我们可以保留第二棵树的右子树，另一颗树作为它的左子树。代码： ```cpp int merge(int A,int B) { if(!A||!B) return A+B; if(rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); update(A); return A; } else { ch[B][0]=merge(A,ch[B][0]); update(B); return B; } } ``` 以上操作完成后，我们就可以用函数式编程的思想完成剩余的操作。 ###插入 直接暴力merge，代码： ```cpp int new_node(int a)//新建一个节点 { size[++cnt]=1; val[cnt]=a; rnd[cnt]=rand(); return cnt; } void insert(int a)//插入 { spilt(root,a,x,y); root=merge(merge(x,new_node(a)),y); } ``` ###删除 删除权值为v的点，先把整颗树以v为权值split成两棵树a,b,再把a树按照v-1分成c,d。这时候值为v的点一定为d的根，那么我们把d的两个子儿子merge起来（划重点：这一步就是去除掉v的影响），再把他们重新merge起来得到一个新的树，这颗树就去除掉了v的影响。代码： ```cpp void del(int a) { split(root,a,x,z); split(x,a-1,x,y); y=merge(ch[y][0],ch[y][1]); root=merge(merge(x,y),z); } ``` ###排名 直接按照a-1的权值把树分开，那么x树中最大的应该小于等于a-1，那么a的排名就是size[x]+1。代码： ```cpp int myrank(int a) { split(root,a-1,x,y); int res=size[x]-1; root=merge(x,y); return res; } ``` ###k小值 不想说什么，直接看代码： ```cpp int findKth(int k) { return val[myrank(root,k)]; } ``` ###前驱后继 我们先看前驱，因为要小于a，所以我们还是按照a-1的权值划分x，现在x中最大的数一定小于等于a-1，所以我们直接输出x中最大的数就好，后继同理，不再赘述。代码： ```cpp int pre(int a) { split(root,a-1,x,y); int res=val[findKth(x,siz[x])]; root=merge(x,y); return res; } int nxt(int a) { split(root,a,x,y); int res=val[findKth(y,1)]; root=merge(x,y); return res; } ``` ###关于区间问题 查询一个区间[l, r]就把一棵树split成三棵树，查中间那棵，再把它们merge回去。代码： ```cpp void add(int l,int r,int delta)//任意操作 { int x,y,z; split(root,x,y,r); split(x,z,x,l-1); addone(x,delta);//任意操作 merge(x,z,x); merge(root,x,y); } ``` ###关于可持久化  fhq treap可以可持久化。如图，每次split和merge走到的所有点都新建一个即可。注意下传标记也要新建点。 ##三道裸题 1.[洛谷P3369 普通~~disco~~平衡树](https://www.luogu.org/problemnew/show/P3369) 就是把上面的东西综合在一起。代码： ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<ctime> #include<cstdlib> #define maxn 500001 using namespace std; int size[maxn],ch[maxn][2],fix[maxn],val[maxn]; int T,cnt,n,m,x,y,z,p,a,root,com; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline void update(int x) { size[x]=1+size[ch[x][0]]+size[ch[x][1]]; } inline int new_node(int x) { size[++cnt]=1; val[cnt]=x; fix[cnt]=rand(); return cnt; } int merge(int A,int B) { if(!A||!B) return A+B; if(fix[A]<fix[B]){ch[A][1]=merge(ch[A][1],B); update(A); return A;} else {ch[B][0]=merge(A,ch[B][0]); update(B); return B;} } void split(int now,int k,int &x,int &y) { if(!now) x=y=0; else { if(val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y); else y=now,split(ch[now][0],k,x,ch[now][0]); update(now); } } int kth(int now,int k) { while(1) { if(k<=size[ch[now][0]]) now=ch[now][0]; else if(k==size[ch[now][0]]+1) return now; else k-=size[ch[now][0]]+1,now=ch[now][1]; } } int main() { srand((unsigned)time(NULL)); T=read(); while(T--) { p=read();a=read(); if(p==1) { split(root,a,x,y); root=merge(merge(x,new_node(a)),y); } else if(p==2) { split(root,a,x,z); split(x,a-1,x,y); y=merge(ch[y][0],ch[y][1]); root=merge(merge(x,y),z); } else if(p==3) { split(root,a-1,x,y); printf("%d\n",size[x]+1); root=merge(x,y); } else if(p==4) printf("%d\n",val[kth(root,a)]); else if(p==5) { split(root,a-1,x,y); printf("%d\n",val[kth(x,size[x])]); root=merge(x,y); } else { split(root,a,x,y); printf("%d\n",val[kth(y,1)]); root=merge(x,y); } } return 0; } ``` 本题还有一种树状数组解法：[树状数组解法](https://www.luogu.org/blog/Chanis/super-BIT2)。 2.[洛谷P3391 文艺平衡树](https://www.luogu.org/problemnew/show/P3391)。 区间操作。代码（感谢[守望](https://www.luogu.org/space/show?uid=49206)的代码）： ```cpp # include<iostream> # include<cstdio> # include<cstring> # include<cstdlib> using namespace std; const int MAX=1e5+1; int n,m,tot,rt; struct Treap{ int pos[MAX],siz[MAX],w[MAX]; int son[MAX][2]; bool fl[MAX]; void pus(int x) { siz[x]=siz[son[x][0]]+siz[son[x][1]]+1; } int build(int x) { w[++tot]=x,siz[tot]=1,pos[tot]=rand(); return tot; } void down(int x) { swap(son[x][0],son[x][1]); if(son[x][0]) fl[son[x][0]]^=1; if(son[x][1]) fl[son[x][1]]^=1; fl[x]=0; } int merge(int x,int y) { if(!x||!y) return x+y; if(pos[x]<pos[y]) { if(fl[x]) down(x); son[x][1]=merge(son[x][1],y); pus(x); return x; } if(fl[y]) down(y); son[y][0]=merge(x,son[y][0]); pus(y); return y; } void split(int i,int k,int &x,int &y) { if(!i) { x=y=0; return; } if(fl[i]) down(i); if(siz[son[i][0]]<k) x=i,split(son[i][1],k-siz[son[i][0]]-1,son[i][1],y); else y=i,split(son[i][0],k,x,son[i][0]); pus(i); } void coutt(int i) { if(!i) return; if(fl[i]) down(i); coutt(son[i][0]); printf("%d ",w[i]); coutt(son[i][1]); } }Tree; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) rt=Tree.merge(rt,Tree.build(i)); for(int i=1;i<=m;i++) { int l,r,a,b,c; scanf("%d%d",&l,&r); Tree.split(rt,l-1,a,b); Tree.split(b,r-l+1,b,c); Tree.fl[b]^=1; rt=Tree.merge(a,Tree.merge(b,c)); } Tree.coutt(rt); return 0; } ``` 3.可持久化序列 可持久化序列这道题要求支持三个操作： 1 l r，翻转l到r的区间； 2 l r，询问l的到r的区间和； 3 p，回到p时刻。 每次修改新建点打翻转标记即可，代码（感谢[permui](http://www.cnblogs.com/owenyu/)的代码）： ```cpp #include<cstdio> #include<cctype> #include<cstring> #include<cstdlib> #include<ctime> #include<utility> #include<algorithm> using namespace std; typedef pair<int,int> Pair; int read() { int x=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=5e4+5; const int nlogn=1.3e7+5; struct node { int x,hp,l,r,sum,size; bool rev; void clear() { x=hp=l=r=sum=size=rev=0; } }; struct TREAP { int pool[nlogn]; int pooler; node t[nlogn]; int now,all; int root[maxn]; TREAP ():now(0),pooler(1) { for (int i=1;i<nlogn;++i) pool[i]=i; root[now]=pool[pooler++]; } int newroot() { int ret=pool[pooler++]; return ret; } int newnode(int x) { int ret=pool[pooler++]; t[ret].hp=rand(); t[ret].size=1; t[ret].x=t[ret].sum=x; return ret; } void delnode(int x) { t[x].clear(); pool[--pooler]=x; } void next() { root[++all]=newroot(); t[root[all]]=t[root[now]]; now=all; } void back(int x) { now=x; } void update(int x) { t[x].sum=t[x].x+t[t[x].l].sum+t[t[x].r].sum; t[x].size=t[t[x].l].size+t[t[x].r].size+1; } void pushdown(int x) { if (!t[x].rev) return; if (t[x].l) { int tx=newnode(t[t[x].l].x); t[tx]=t[t[x].l]; t[tx].rev^=true; t[x].l=tx; } if (t[x].r) { int tx=newnode(t[t[x].r].x); t[tx]=t[t[x].r]; t[tx].rev^=true; t[x].r=tx; } swap(t[x].l,t[x].r); t[x].rev=false; } int merge(int x,int y) { if (!x) return y; if (!y) return x; int now; if (t[x].hp<=t[y].hp) { now=newnode(t[x].x); t[now]=t[x]; pushdown(now); t[now].r=merge(t[now].r,y); } else { now=newnode(t[y].x); t[now]=t[y]; pushdown(now); t[now].l=merge(x,t[now].l); } update(now); return now; } Pair split(int x,int p) { if (t[x].size==p) return make_pair(x,0); int now=newnode(t[x].x); t[now]=t[x]; pushdown(now); int l=t[now].l,r=t[now].r; if (t[l].size>=p) { t[now].l=0; update(now); Pair g=split(l,p); now=merge(g.second,now); return make_pair(g.first,now); } else if (t[l].size+1==p) { t[now].r=0; update(now); return make_pair(now,r); } else { t[now].r=0; update(now); Pair g=split(r,p-t[l].size-1); now=merge(now,g.first); pushdown(now); return make_pair(now,g.second); } } void rever(int l,int r) { ++l,++r; Pair g=split(root[now],l-1); Pair h=split(g.second,r-l+1); int want=h.first; int here=newnode(t[want].x); t[here]=t[want]; t[here].rev^=true; int fi=merge(g.first,here); int se=merge(fi,h.second); root[now]=se; } int query(int l,int r) { ++l,++r; Pair g=split(root[now],l-1); Pair h=split(g.second,r-l+1); int want=h.first; int ret=t[want].sum; int fi=merge(g.first,want); int se=merge(fi,h.second); root[now]=se; return ret; } void insert(int x) { int k=newnode(x); root[now]=merge(root[now],k); } } Treap; int main() { #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); freopen("my.out","w",stdout); #endif srand(time(0)); int n=read(),m=read(); for (int i=1;i<=n;++i) { int x=read(); Treap.insert(x); } while (m--) { int op=read(); if (op==1) { Treap.next(); int l=read(),r=read(); Treap.rever(l,r); } else if (op==2) { int l=read(),r=read(); int ans=Treap.query(l,r); printf("%d\n",ans); } else if (op==3) { Treap.back(read()); } } return 0; } ``` ##作业 1.[洛谷P2596 书架](https://www.luogu.org/problemnew/show/P2596) 2.[洛谷P4309 最长上升子序列](https://www.luogu.org/problemnew/show/P4309) 3.[洛谷P3987 我永远喜欢珂朵莉~](https://www.luogu.org/problemnew/show/P3987) 4.[洛谷P3920 紫荆花之恋](https://www.luogu.org/problemnew/show/P3920)（在做此题前，你需要掌握[点分治](https://www.luogu.org/blog/user9012/dian-fen-zhi-lve-xie)，你还需要一点替罪羊树的思想，不难，就是当一个点过于不平衡时，我们就拍掉重建）。 ##完结撒花！*★,°*:.☆(￣▽￣)/$:*.°★* 。