fhq-treap，也即非旋treap，可以在不進行旋轉操作的前提下維護treap。由于不需要旋轉，可以對其可持久化。

　　fhq-treap的基本操作是merge和split，并且通過這兩個操作實現對treap的各項維護。

　　merge用來合并兩棵treap，且要求滿足其中一棵treap中的最大值小于另一棵treap中的最小值。實現方式類似于左偏樹，即每次考慮合并以x為根和以y為根的子樹（不妨令x子樹中的值較小）。因為要維持treap自身的性質，合并后應該以x和y中優先級較高的為根。如果x優先級較高，繼續將x的右子樹與y合并，再將所得子樹作為x的右子樹；如果y優先級較高，繼續將y的左子樹與x合并，再將所得子樹作為y的左子樹。這里就可以進行可持久化。因為樹高是期望log的，合并復雜度即為log。

　　split用來將一棵treap分裂為兩棵，且分裂后使得前k小的作為一棵treap，剩下的作為另一棵。具體地，分裂以x為根的子樹時，考慮前k小的所處位置。如果左子樹大小恰好為k，分裂后直接退出；如果左子樹大小>k，顯然應該進入左子樹繼續操作，分裂后返回兩棵treap的根，其中一棵接到已分裂好的原treap上。另一種情況類似。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 500010 #define inf 2147483647 #define pii pair<int,int> #define lson tree[k].ch[0] #define rson tree[k].ch[1] char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,root[N],cnt; struct data{int ch[2],x,p,s; }tree[N<<6]; void up(int k){tree[k].s=tree[lson].s+tree[rson].s+1;} int qnum(int k,int x) {if (tree[lson].s+1==x) return tree[k].x;if (tree[lson].s+1>x) return qnum(lson,x);else return qnum(rson,x-tree[lson].s-1); } int qrank(int k,int x) {if (!k) return 0;if (tree[k].x>=x) return qrank(lson,x);else return tree[lson].s+1+qrank(rson,x); } int qpre(int k,int x) {if (!k) return -inf;if (tree[k].x>=x) return qpre(lson,x);else return max(tree[k].x,qpre(rson,x)); } int qsuf(int k,int x) {if (!k) return inf;if (tree[k].x<=x) return qsuf(rson,x);else return min(tree[k].x,qsuf(lson,x)); } int merge(int x,int y) {if (!x||!y) return x|y;int k=++cnt;if (tree[x].p>tree[y].p){tree[k]=tree[x];rson=merge(rson,y);}else{tree[k]=tree[y];lson=merge(x,lson);}up(k);return k; } pii split(int k,int x) {if (!k) return make_pair(0,0);int u=++cnt;tree[u]=tree[k];if (tree[tree[u].ch[0]].s==x) return tree[u].ch[0]=0,up(u),make_pair(lson,u);if (tree[tree[u].ch[0]].s>x){pii v=split(tree[u].ch[0],x);return tree[u].ch[0]=v.second,up(u),make_pair(v.first,u);}else{pii v=split(tree[u].ch[1],x-tree[tree[u].ch[0]].s-1);return tree[u].ch[1]=v.first,up(u),make_pair(u,v.second);} } int newpoint(int x) {cnt++;tree[cnt].x=x,tree[cnt].p=rand(),tree[cnt].s=1,tree[cnt].ch[0]=tree[cnt].ch[1]=0;return cnt; } int main() { #ifndef ONLINE_JUDGEfreopen("fhqtreap.in","r",stdin);freopen("fhqtreap.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifsrand(20020509);m=read();for (int i=1;i<=m;i++){int last=read(),op=read(),x=read();root[i]=root[last];switch (op){case 1:{int u=qrank(root[i],x),v=newpoint(x);pii p=split(root[i],u);root[i]=merge(merge(p.first,v),p.second);break;}case 2:{int p=qrank(root[i],x);if (qnum(root[i],p+1)==x){pii u=split(root[i],p),v=split(u.second,1);root[i]=merge(u.first,v.second);}break;}case 3:{printf("%d\n",qrank(root[i],x)+1);break;}case 4:{printf("%d\n",qnum(root[i],x));break;}case 5:{printf("%d\n",qpre(root[i],x));break;}case 6:{printf("%d\n",qsuf(root[i],x));break;}}//for (int j=1;j<=m;j++) cout<<root[j]<<' ';cout<<endl;//for (int j=1;j<=cnt;j++) cout<<tree[j].x<<' '<<tree[j].s<<' '<<tree[j].ch[0]<<' '<<tree[j].ch[1]<<endl;cout<<endl; }return 0; }

?

轉載于:https://www.cnblogs.com/Gloid/p/10249484.html

總結

以上是生活随笔為你收集整理的Luogu3835 【模板】可持久化平衡树（fhq-treap）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。