题目概述

CFGYM102566L

解题报告

如果没有询问路径就是很裸的平衡树维护DFS序，对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$ ，就可以方便的维护出DFS序。

套路：将 $x\to fa_x$ 的边权挂在 $x$ 上，如果 $x$ 权值为 $w$ ，令 $x_{in}$ 权值为 $w$ ，$x_{out}$ 权值也为 $w$ 。则 $x\to y$ 路径边权异或和可以转化为 $[x_{in}+1,y_{in}]$ 的权值异或和。

因此在Splay上维护 $ex_x,A_x,B_x$ ，其中 $ex_x$ 表示 $x$ 是否是入栈节点，$A_x$ 表示 $x$ 子树中入栈节点的权值异或和，$B_x$ 表示 $x$ 子树中的权值异或和。用 $A_x$ 查询子树和，$B_x$ 查询路径和即可。

然后有个需要注意的地方是 $1$ 操作，$1$ 操作时会导致大量树上父亲信息变化，因此可以使用并查集来快速查询真正的父亲。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=250000,maxx=1000000,maxt=(maxx<<1)+10;

int te,lt[maxx+5],rt[maxx+5],fat[maxx+5],father[maxx+5];
int pl,ro,son[maxt+5][2],fa[maxt+5],si[maxt+5];
int cnt[maxt+5];bool ex[maxt+5];
int w[maxt+5],sum[maxt+5],pre[maxt+5],tag[maxt+5];

int newnode(bool fl) {pl++;si[pl]=1;cnt[pl]=ex[pl]=fl;return pl;}
int cmp(int p,int &k){
    if (k<=si[son[p][0]]) return 0;
    if (k==si[son[p][0]]+1) return -1;
    k-=si[son[p][0]]+1;return 1;
}
void Pushup(int p){
    si[p]=si[son[p][0]]+1+si[son[p][1]];
    cnt[p]=cnt[son[p][0]]+ex[p]+cnt[son[p][1]];
    sum[p]=sum[son[p][0]]^(ex[p]?w[p]:0)^sum[son[p][1]];
    pre[p]=pre[son[p][0]]^w[p]^pre[son[p][1]];
}
void Rotate(int &p,int d){
    int t=son[p][d];
    son[p][d]=son[t][d^1];son[t][d^1]=p;
    Pushup(p);Pushup(t);
    if (son[p][d]) fa[son[p][d]]=p;
    fa[t]=fa[p];fa[p]=t;p=t;
}
void Addtag(int p,int k){
    if (!p) return;
    w[p]^=k;
    if (cnt[p]&1) sum[p]^=k;
    if (si[p]&1) pre[p]^=k;
    tag[p]^=k;
}
void Pushdown(int p) {if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;}
void Splay(int &p,int k){
    int d=cmp(p,k);Pushdown(p);if (d<0) return;
    int &t=son[p][d],f=cmp(t,k);Pushdown(t);
    if (~f) Splay(son[t][f],k),d==f?Rotate(p,d):Rotate(t,f);
    Rotate(p,d);
}
int Askrk(int p){
    static int top=0,stk[maxt+5];
    for (int i=p;i!=ro;i=fa[i]) stk[++top]=fa[i];
    while (top) Pushdown(stk[top--]);
    int rk=si[son[p][0]]+1;
    for (int f=fa[p];p!=ro;p=f,f=fa[p])
        if (p==son[f][1]) rk+=si[son[f][0]]+1;
    Splay(ro,rk);return rk;
}
void Make(int x,int W){
    lt[x]=newnode(1);rt[x]=newnode(0);
    son[lt[x]][1]=rt[x];fa[rt[x]]=lt[x];
    w[lt[x]]=w[rt[x]]=W;
    Pushup(rt[x]);Pushup(lt[x]);
}
int getseg(int L,int R){
    L--;R++;Splay(ro,L);cmp(ro,R);Splay(son[ro][1],R);
    return son[son[ro][1]][0];
}
void Insert(int rk,int y){
    int p=getseg(rk,rk);
    son[p][1]=y;fa[y]=p;
    Pushup(p);Pushup(son[ro][1]);Pushup(ro);
}
int Delete(int L,int R){
    int p=getseg(L,R);
    son[son[ro][1]][0]=0;fa[p]=0;
    Pushup(son[ro][1]);Pushup(ro);
    return p;
}
int getfa(int x) {return x==father[x]?x:father[x]=getfa(father[x]);}
int main(){
    Make(0,0);
    int p=newnode(0);
    son[rt[0]][1]=p;fa[p]=rt[0];
    p=newnode(0);
    son[lt[0]][0]=p;fa[p]=lt[0];
    Pushup(rt[0]);Pushup(lt[0]);
    ro=lt[0];
    for (int i=0;i<=maxx;i++) father[i]=i;
    for (scanf("%d",&te);te;te--){
        int tp,x,y,z,rk,p,L,R;
        scanf("%d%d",&tp,&x);
        if (tp==0){
            scanf("%d%d",&y,&z);
            Make(x,z);
            rk=Askrk(lt[y]);
            Insert(rk,lt[x]);fat[x]=y;
        } else if (tp==1){
            p=getseg(Askrk(lt[x]),Askrk(rt[x]));
            rk=Askrk(lt[x]);Delete(rk,rk);
            rk=Askrk(rt[x]);Delete(rk,rk);
            father[x]=getfa(fat[x]);
        } else if (tp==2){
            scanf("%d",&y);
            int F=getfa(fat[x]);
            Askrk(lt[F]);
            L=Askrk(lt[x]),R=Askrk(rt[x]);
            p=Delete(L,R);
            rk=Askrk(lt[y]);
            Insert(rk,p);fat[x]=y;
        } else if (tp==3){
            scanf("%d",&z);
            L=Askrk(lt[x]),R=Askrk(rt[x]);
            p=getseg(L,L);Addtag(p,z);
            Pushup(son[ro][1]);Pushup(ro);
            p=getseg(R,R);Addtag(p,z);
            Pushup(son[ro][1]);Pushup(ro);
            p=getseg(L,R);Addtag(p,z);
            Pushup(son[ro][1]);Pushup(ro);
        } else if (tp==4){
            p=getseg(Askrk(lt[x]),Askrk(rt[x]));
            printf("%d\n",sum[p]^w[lt[x]]);
        } else if (tp==5){
            scanf("%d",&y);
            L=Askrk(lt[x]);R=Askrk(lt[y]);
            if (L>R) swap(L,R);L++;
            printf("%d\n",pre[getseg(L,R)]);
        }
    }
    return 0;
}