题解 P5055 【【模板】可持久化文艺平衡树】

· · 题解

我用了一种类似于支持区间修改的可持久化线段树的方法，也就是标记永久化。看到大家的做法都是在下放标记的时候把节点复制一遍，觉得这样很不爽啊……我想，能不能干脆把标记永久化，节约一些空间和时间呢？

实现的关键在于merge和split这两个函数。

split

假设我们现在要把以x为根的这一棵子树，中序遍历的序列中的前k个节点分到第一棵treap中去，后n-k个节点分到第二棵treap中去。假设x的子树内的点，应该分到第一棵treap中的a节点的位置，应该分到第二棵treap中的b节点的位置。

我们记tag_x为要分离的这一棵treap中，从根节点到x的父亲标记累加的结果；记tag_a为第一棵treap中，从根节点到a点的父亲标记累加的结果；记tag_b为从根节点到b点的父亲标记累加的结果。我们记rev_i为i这个点的标记，其中rev_i=1表示这个子树内的点需要翻转，rev_i=0表示这个子树内的点不需要翻转。

那么，假如x的左儿子的大小大于等于k，也就是说，x属于第二棵treap，并且x的右儿子全部属于第二棵treap，那么，我们应该把x这个点放在b这个位置，然后递归分离x的左儿子（此时第二棵树中对应的位置就是b的左儿子了）。考虑标记，我们需要保证，第二棵树中tag_b \text{ xor } rev_b = tag_x \text { xor } rev_x 。我们令rev_b = tag_x \text{ xor } rev_x \text { xor } tag_b 即可。

左儿子的大小小于k也是同理，我们令rev_a = tag_x \text{ xor } rev_x \text{ xor } tag_a即可。

注意，如果从根节点到某个点x，标记叠加的结果是tg，假如原来我们用ch_{x,0}表示x的左儿子，ch_{x,1}表示某个点的右儿子，那么现在x的左儿子应该表示为ch_{x,tg}，右儿子则是ch_{x,tg\text{ xor }1}。

int tx,ta,tb;
void split(int x,int k,int &a,int &b)
{
    if(!x){a=b=0; return;} tx^=rev[x];
    if(sz[ch[x][tx]]>=k)
    {
        rev[b=cpy(x)]=tb^tx,tb=tx;
        split(ch[x][tx],k,a,ch[b][tb]),push_up(b);
    }
    else
    {
        rev[a=cpy(x)]=ta^tx,ta=tx;
        split(ch[x][tx^1],k-sz[ch[x][tx]]-1,ch[a][ta^1],b),push_up(a);
    }
}

merge

我们假设现在要把第一棵treap中以a为根的这个子树，以及第二棵treap中以b为根的这一棵子树，合并到r这个节点上。

我们仍然记tag_a为第一棵treap中，从根节点到a这个节点的父亲，标记累加的结果；设tag_b为第二棵treap中从根节点到b这个节点的父亲，标记累加的结果；设tag_r为合并后得到的树中，从根节点到r节点的父亲，标记累加的结果。

假如现在key_a\le key_b，即应该把a节点放到r这个位置，把a的右儿子和b合并。这个时候我们必须保证从合并后的树的根到r（也就是a）的这条路径上，标记累加的结果等于tag_a\text{ xor } rev_a。那么我们就令r这个节点的标记等于tag_a\text{ xor } rev_a \text { xor } tag_r，这样就有rev_r \text{ xor } tag_r =tag_a \text { xor } rev_a。然后递归合并a的右儿子和b即可。

对于key_a >key_b的情况也是同理，我们需要保证从合并后的树的根到r的这条路径上，标记累加的结果等于tag_b\text{ xor } rev_b。令rev_r = tag_b\text{ xor } rev_b \text{ xor } tag_r即可。

注意我们split的时候，第一棵树的整条最右链和第二棵树的最左链上的节点都是复制过了的，而在merge的时候显然也只会用到第一棵树的最右链和第二棵树的最左链，所以在merge的过程中不需要复制节点。

int tx,ta,tb;
void merge(int &r,int a,int b)
{
    if(!a||!b)
    {
        if(a) ta^=rev[a],rev[r=a]=tx^ta;
        else if(b) tb^=rev[b],rev[r=b]=tx^tb;
        else r=0;
        return;
    }
    if(key[a]<=key[b])
    {
        ta^=rev[a],rev[r=a]=tx^ta,tx=ta;
        merge(ch[r][tx^1],ch[a][ta^1],b);
    }
    else
    {
        tb^=rev[b],rev[r=b]=tx^tb,tx=tb;
        merge(ch[r][tx],a,ch[b][tb]);
    }
    push_up(r);
}

下面是我巨丑无比的完整代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
#define uint unsigned int
#define done tx=ta=tb=0
using namespace std;
template <class T>
inline void read(T &x)
{
    x=0; char c=getchar();  int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
uint seed=19260817;
uint Rand()
{
    seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;
    return seed;
}
const int N=2e5+10,M=N*66;
int rt[N],ch[M][2],val[M],rev[M],sz[M],ncnt;
ll sum[M];
uint key[M];
void push_up(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1,sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];}
int stk[M],top;
int make(int v)
{
    int u=top?stk[top--]:++ncnt;
    ch[u][0]=ch[u][1]=rev[u]=0;
    val[u]=sum[u]=v,key[u]=Rand(),sz[u]=1;
    return u;
}
int cpy(int c)
{
    int u=top?stk[top--]:++ncnt;
    ch[u][0]=ch[c][0],ch[u][1]=ch[c][1],rev[u]=rev[c];
    val[u]=val[c],sum[u]=sum[c],key[u]=key[c],sz[u]=sz[c];
    return u;
}
int tx,ta,tb;
void merge(int &r,int a,int b)
{
    if(!a||!b)
    {
        if(a) ta^=rev[a],rev[r=a]=tx^ta;
        else if(b) tb^=rev[b],rev[r=b]=tx^tb;
        else r=0;
        return;
    }
    if(key[a]<=key[b])
    {
        ta^=rev[a],rev[r=a]=tx^ta,tx=ta;
        merge(ch[r][tx^1],ch[a][ta^1],b);
    }
    else
    {
        tb^=rev[b],rev[r=b]=tx^tb,tx=tb;
        merge(ch[r][tx],a,ch[b][tb]);
    }
    push_up(r);
}
void split(int x,int k,int &a,int &b)
{
    if(!x){a=b=0; return;} tx^=rev[x];
    if(sz[ch[x][tx]]>=k)
    {
        rev[b=cpy(x)]=tb^tx,tb=tx;
        split(ch[x][tx],k,a,ch[b][tb]),push_up(b);
    }
    else
    {
        rev[a=cpy(x)]=ta^tx,ta=tx;
        split(ch[x][tx^1],k-sz[ch[x][tx]]-1,ch[a][ta^1],b),push_up(a);
    }
}

void insert(int r1,int &r2,int p,int v)
{
    int x,y; done; split(r1,p,x,y);
    done; merge(r2,x,make(v)); done; merge(r2,r2,y);
}
void del(int r1,int &r2,int p)
{
    int x,y,z; done; split(r1,p,x,y); done; split(x,p-1,x,z);
    stk[++top]=z; done; merge(r2,x,y);
}
void Reverse(int r1,int &r2,int l,int r)
{
    int x,y,z; done; split(r1,l-1,x,y); done; split(y,r-l+1,y,z);
    rev[y]^=1; done; merge(r2,x,y); done; merge(r2,r2,z);
}
ll query(int r1,int l,int r)
{
    int x,y,z; done; split(r1,l-1,x,y); done; split(y,r-l+1,y,z);
    return sum[y];
}
int main()
{
    int q,v,op,x,l,r; ll lst=0; read(q);
    for(int i=1;i<=q;++i)
    {
        read(v),read(op);
        if(op==1)
        {
            read(l),read(x); l^=lst,x^=lst;
            insert(rt[v],rt[i],l,x);
        }
        else if(op==2)
        {
            read(l); l^=lst;
            del(rt[v],rt[i],l);
        }
        else if(op==3)
        {
            read(l),read(r); l^=lst,r^=lst;
            Reverse(rt[v],rt[i],l,r);
        }
        else
        {
            read(l),read(r); l^=lst,r^=lst;
            printf("%lld\n",lst=query(rt[v],l,r)),rt[i]=rt[v];
        }

    }
    return 0;
}