洛谷P5055 可持久化文艺平衡树 (可持久化treap)

文艺平衡树的可持久化版，可以使用treap实现。

作为序列使用的treap相对splay的优点如下：

1.代码短

2.容易实现可持久化

3.边界处理方便（splay常常需要在左右两端加上保护结点以防越界，而treap一般不用）

可以分裂合并的treap一般称作无旋treap或FHQ-treap，不过我个人觉得它的结构和普通的treap没什么两样，只是多了个分裂和合并的操作而已...

代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e7+,inf=0x3f3f3f3f;

 int ch[N][],val[N],siz[N],rd[N],rev[N],tot,n,m,rt[N];

 ll sum[N];

 #define l(u) ch[u][0]

 #define r(u) ch[u][1]

 int newnode(int x) {int u=++tot; val[u]=sum[u]=x,siz[u]=,rd[u]=rand(),l(u)=r(u)=rev[u]=; return u;}

 int cpy(int u) {int w=++tot; val[w]=val[u],sum[w]=sum[u],rd[w]=rd[u],siz[w]=siz[u],rev[w]=rev[u],l(w)=l(u),r(w)=r(u); return w;}

 void pu(int u) {siz[u]=siz[l(u)]+siz[r(u)]+,sum[u]=sum[l(u)]+sum[r(u)]+val[u];}

 void pd(int u) {

     if(rev[u]) {

         rev[u]=;

         if(l(u))l(u)=cpy(l(u));

         if(r(u))r(u)=cpy(r(u));

         swap(l(u),r(u));

         rev[l(u)]^=,rev[r(u)]^=;

     }

 }

 void sp(int w,int k,int& u,int& v) {

     if(!w) {u=v=; return;}

     pd(w);

     if(k>=siz[l(w)]+)u=cpy(w),sp(r(w),k-(siz[l(w)]+),r(u),v),pu(u);

     else v=cpy(w),sp(l(w),k,u,l(v)),pu(v);

 }

 void mg(int& w,int u,int v) {

     if(!u||!v) {w=u|v; return;}

     if(rd[u]>rd[v])pd(u),w=u,mg(r(w),r(u),v);

     else pd(v),w=v,mg(l(w),u,l(v));

     pu(w);

 }

 void rv(int& u,int l,int r) {

     int L,M,R;

     sp(u,r,L,R),sp(L,l-,L,M);

     rev[M]^=;

     mg(u,L,M),mg(u,u,R);

 }

 void ins(int& u,int p,int x) {

     int L,M,R;

     sp(u,p,L,R),mg(L,L,newnode(x)),mg(u,L,R);

 }

 void del(int& u,int p) {

     int L,M,R;

     sp(u,p,L,R),sp(L,p-,L,M),mg(u,L,R);

 }

 ll qry(int& u,int l,int r) {

     int L,M,R;

     sp(u,r,L,R),sp(L,l-,L,M);

     ll ret=sum[M];

     mg(L,L,M),mg(u,L,R);

     return ret;

 }

 int main() {

     srand(time());

     scanf("%d",&n);

     ll last=;

     for(int i=; i<=n; ++i) {

         int a,b,c,d;

         scanf("%d%d%d",&a,&b,&c),c^=last;

         if(b!=)scanf("%d",&d),d^=last;

         rt[i]=rt[a];

         if(b==)ins(rt[i],c,d);

         else if(b==)del(rt[i],c);

         else if(b==)rv(rt[i],c,d);

         else printf("%lld\n",last=qry(rt[i],c,d));

     }

     return ;

 }

还有一种实现方法是去掉每个结点的随机因子，在合并的时候改用rand函数来决定哪个结点作为哪个节点的父亲，判断rand()%(siz[u]+siz[v])和siz[u]的大小关系就行了。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e7+,inf=0x3f3f3f3f;

 int ch[N][],val[N],siz[N],rev[N],tot,n,m,rt[N];

 ll sum[N];

 #define l(u) ch[u][0]

 #define r(u) ch[u][1]

 int newnode(int x) {int u=++tot; val[u]=sum[u]=x,siz[u]=,l(u)=r(u)=rev[u]=; return u;}

 int cpy(int u) {int w=++tot; val[w]=val[u],sum[w]=sum[u],siz[w]=siz[u],rev[w]=rev[u],l(w)=l(u),r(w)=r(u); return w;}

 void pu(int u) {siz[u]=siz[l(u)]+siz[r(u)]+,sum[u]=sum[l(u)]+sum[r(u)]+val[u];}

 void pd(int u) {

     if(rev[u]) {

         rev[u]=;

         if(l(u))l(u)=cpy(l(u));

         if(r(u))r(u)=cpy(r(u));

         swap(l(u),r(u));

         rev[l(u)]^=,rev[r(u)]^=;

     }

 }

 void sp(int w,int k,int& u,int& v) {

     if(!w) {u=v=; return;}

     pd(w);

     if(k>=siz[l(w)]+)u=cpy(w),sp(r(w),k-(siz[l(w)]+),r(u),v),pu(u);

     else v=cpy(w),sp(l(w),k,u,l(v)),pu(v);

 }

 void mg(int& w,int u,int v) {

     if(!u||!v) {w=u|v; return;}

     if(rand()%(siz[u]+siz[v])<siz[u])pd(u),w=u,mg(r(w),r(u),v);

     else pd(v),w=v,mg(l(w),u,l(v));

     pu(w);

 }

 void rv(int& u,int l,int r) {

     int L,M,R;

     sp(u,r,L,R),sp(L,l-,L,M);

     rev[M]^=;

     mg(u,L,M),mg(u,u,R);

 }

 void ins(int& u,int p,int x) {

     int L,M,R;

     sp(u,p,L,R),mg(L,L,newnode(x)),mg(u,L,R);

 }

 void del(int& u,int p) {

     int L,M,R;

     sp(u,p,L,R),sp(L,p-,L,M),mg(u,L,R);

 }

 ll qry(int& u,int l,int r) {

     int L,M,R;

     sp(u,r,L,R),sp(L,l-,L,M);

     ll ret=sum[M];

     mg(L,L,M),mg(u,L,R);

     return ret;

 }

 int main() {

     srand(time());

     scanf("%d",&n);

     ll last=;

     for(int i=; i<=n; ++i) {

         int a,b,c,d;

         scanf("%d%d%d",&a,&b,&c),c^=last;

         if(b!=)scanf("%d",&d),d^=last;

         rt[i]=rt[a];

         if(b==)ins(rt[i],c,d);

         else if(b==)del(rt[i],c);

         else if(b==)rv(rt[i],c,d);

         else printf("%lld\n",last=qry(rt[i],c,d));

     }

     return ;

 }

巴特西

洛谷P5055 可持久化文艺平衡树 (可持久化treap)

最新文章

热门文章