无旋treap

无旋treap,又名fhq_treap是范浩强巨佬发明的不用旋转维护treap性质的神奇数据结构，比起普通treap，可以解决许多区间操作问题，还可持久化，代码也简单

例一：普通平衡树tyvj1728（treap模板）

如果想看旋转treap怎么写戳这儿 无旋treap代码：

#include<bits/stdc++.h> using namespace std; const int N=5e5+5; struct node{ int val,ch[2],size,rd; #define l(x) t[x].ch[0] #define r(x) t[x].ch[1] }t[N]; struct treap{ int root,x,y,z,cnt; inline void up(int x){ t[x].size=1+t[l(x)].size+t[r(x)].size; } inline int new_node(int x){ t[++cnt].size=1; t[cnt].val=x; t[cnt].rd=rand(); return cnt; } void split(int now,int k,int &x,int &y){ if(!now)x=y=0; else{ if(t[now].val<=k)x=now,split(r(now),k,r(now),y); else y=now,split(l(now),k,x,l(now)); up(now); } } int merge(int A,int B){ if(!A||!B)return A+B; if(t[A].rd<t[B].rd){ t[A].ch[1]=merge(r(A),B);up(A); return A; } else{ t[B].ch[0]=merge(A,l(B));up(B); return B; } } int kth(int now,int k){ while(1){ if(k<=t[l(now)].size)now=l(now); else if(k==t[l(now)].size+1)return now; else k-=t[l(now)].size+1,now=r(now); } } void insert(int a){ split(root,a,x,y); root=merge(merge(x,new_node(a)),y); } void shan(int a){ split(root,a,x,z); split(x,a-1,x,y); y=merge(l(y),r(y)); root=merge(merge(x,y),z); } int rank(int a){ split(root,a-1,x,y); int ans=t[x].size+1; root=merge(x,y); return ans; } int pre(int a){ split(root,a-1,x,y); int ans=t[kth(x,t[x].size)].val; root=merge(x,y); return ans; } int nxt(int a){ split(root,a,x,y); int ans=t[kth(y,1)].val; root=merge(x,y); return ans; } }tr; 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; } int main(){ srand(time(0)); int T=read(); while(T--){ int p=read(),a=read(); if(p==1)tr.insert(a); if(p==2)tr.shan(a); if(p==3)printf("%d\n",tr.rank(a)); if(p==4)printf("%d\n",t[tr.kth(tr.root,a)].val); if(p==5) printf("%d\n",tr.pre(a)); if(p==6)printf("%d\n",tr.nxt(a)); } return 0; }

注意读优负数

例二：文艺平衡树（翻转操作）

很简单，用无旋treap存一存下标号，每次翻转时将树分成1-l-1,l-r,r+1-n三部分，对中间一部分进行操作即可 翻转操作：标记一下就可以，注意做所有操作都会改变树的形态，记得下传标记与上传字数大小

整个过程很顺利，80行搞定（比t1还短），真心比SPLAY好些10000倍 这就是fhq_treap的优势 代码：

#include<bits/stdc++.h> using namespace std; const int N=5e5+5; int ch[N][2],tag[N],val[N],siz[N],key[N],root; int n,m,tot; #define l(x) ch[x][0] #define r(x) ch[x][1] 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 up(int x){ siz[x]=siz[l(x)]+siz[r(x)]+1; } inline void pushdown(int x){ if(tag[x]){ tag[l(x)]^=1;tag[r(x)]^=1; swap(l(x),r(x)); tag[x]^=1; } } inline int makenode(int x){ siz[++tot]=1; val[tot]=x; key[tot]=rand(); return tot; } int merge(int x,int y){ if(!x||!y)return x+y; pushdown(x);pushdown(y); if(key[x]<key[y]){ r(x)=merge(r(x),y); up(x);return x; } l(y)=merge(x,l(y)); up(y);return y; } void split(int now,int k,int &x,int &y){ if(!now){ x=y=0;return ; } else{ pushdown(now); if(k<=siz[l(now)]) y=now,split(l(now),k,x,l(now)); else x=now,split(r(now),k-siz[l(now)]-1,r(now),y); up(now); } } void rever(int l,int r){ int a,b,c,d; split(root,r,a,b); split(a,l-1,c,d); tag[d]^=1; root=merge(merge(c,d),b); } void print(int x){ if(!x)return ; pushdown(x); print(l(x)); printf("%d ",val[x]); print(r(x)); } int main(){ n=read();m=read(); for(int i=1;i<=n;i++) root=merge(root,makenode(i)); while(m--){ int a=read(),b=read();; rever(a,b); } print(root); return 0; }

总结：fhq_treap的优劣势

优势： 1.代码非常非常非常极其极其极其简单（比带旋treap都简单） 2.可持久化（因为不涉及旋转）

劣势： 1.速度有点慢，是个问题（不过做这些题还是绰绰有余），但树套树的时候一定 要小心常数 2.维护LCT(虽然我也不会）比SPLAY维护多以个log(n)

完结散花