【Ynoi2010】Fusion tree

mrsrz 1月 29, 2020

01Trie。

题目大意：

给定一棵树，点带点权，要求支持以下操作：

给定 $x$，令与 $x$ 相邻的所有结点的点权加上 $1$。
给定 $x,v$，令 $x$ 的点权减少 $v$。
给定 $x$，求与 $x$ 相邻的所有结点的点权的 xor 和。

题解：

取一个结点作为根，每个结点用 01 Trie 存储所有儿子结点的值，并记录它们的 xor 和。这里我们从低位到高位插入。

我们需要先做到单点查询。对于操作 $2$ 直接改，对于操作 $1$，我们拆成对儿子的贡献和对父亲的贡献。对父亲的贡献相当于单点修改，对儿子的贡献，我们记录每个点被操作的次数，然后查询一个结点的点权的时候，加上父亲被操作的次数即可。时间复杂度 $O(1)$。

然后考虑维护 xor 和。

对于操作 $2$，我们把原来的值从 Trie 中删除，把新的值插入，同时修改 xor 和。时间复杂度 $O(\log n)$。

对于操作 $1$，关于父亲的，直接做一次单点修改。关于儿子的，我们对这个结点保存的 Trie 树整体考虑。这个操作相当于，对最低位为 $0$ 的变为 $1$，对最低位为 $1$ 的变为 $0$ 的同时，这部分数的下一位再进行相同的操作。直接递归即可。时间复杂度 $O(\log n)$。修改的同时更新全局 xor 和。

对于操作 $3$，直接取 $x$ 的儿子的全局 xor 和，再异或上 $x$ 的父亲的点权即可。时间复杂度 $O(1)$。

故总时间复杂度 $O((n+m)\log n)$。

Code：

#include<iostream>
#include<cassert>
#include<algorithm>
using namespace std;
const int N=5e5+5,M=N*40;
int ch[M][2],nod,sz[M],rt[N],head[N],cnt,n,m,fa[N];
int A[N],tag[N],X[N];
struct edge{
    int to,nxt;
}e[N<<1];
void dfs(int now,int pre=0){
    for(int i=head[now];i;i=e[i].nxt)
    if(e[i].to!=pre){
        fa[e[i].to]=now;
        dfs(e[i].to,now);
    }
}
void insert(int id,int v){
    X[id]^=v;
    if(!rt[id])rt[id]=++nod;
    int nw=rt[id];
    for(int i=0;i<20;++i){
        ++sz[nw];
        const bool c=v>>i&1;
        if(!ch[nw][c])ch[nw][c]=++nod;
        nw=ch[nw][c];
    }
    ++sz[nw];
}
void erase(int id,int v){
    X[id]^=v;
    assert(rt[id]);
    int nw=rt[id];
    for(int i=0;i<20;++i){
        --sz[nw];
        const bool c=v>>i&1;
        if(!ch[nw][c])ch[nw][c]=++nod;
        nw=ch[nw][c];
    }
    --sz[nw];
}
void modify(int id){
    int nw=rt[id];
    for(int i=0;i<20&&nw;++i){
        int&_0=ch[nw][0],&_1=ch[nw][1];
        X[id]^=(1<<i)*((sz[_0]&1)^(sz[_1]&1));
        nw=_1;
        swap(_0,_1);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    dfs(1);
    for(int i=1;i<=n;++i){
        cin>>A[i];
        if(fa[i])insert(fa[i],A[i]);
    }
    while(m--){
        int op,x;
        cin>>op>>x;
        switch(op){
            case 1:{
                int y=fa[x];
                if(y){
                    if(fa[y])erase(fa[y],A[y]+tag[fa[y]]);
                    ++A[y];
                    if(fa[y])insert(fa[y],A[y]+tag[fa[y]]);
                }
                ++tag[x];
                modify(x);
                break;
            }
            case 2:{
                int v;
                cin>>v;
                if(fa[x])erase(fa[x],A[x]+tag[fa[x]]);
                A[x]-=v;
                if(fa[x])insert(fa[x],A[x]+tag[fa[x]]);
                break;
            }
            case 3:{
                cout<<(X[x]^(A[fa[x]]+tag[fa[fa[x]]]))<<'\n';
                break;
            }
        }
    }
    return 0;
}