2019 ACM-ICPC 西安全国邀请赛 E-Tree 树链剖分+线段树

题意

给一颗带点权的树，三种操作

• \(1~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]|t\)
• \(2~s~t\) 修改从1到s的路径上的所有点，\(a[i]=a[i]\&t\)
• \(3~s~t\) 询问将1到s的路径上的所有点作为石头堆，再加上一个个数为\(t\)的石头堆，进行一次尼姆博弈，先手胜利输出YES，否则输出NO

分析

尼姆博弈先手必胜条件为所有石头堆异或和为0，将询问转化为求1到s的路径上的所有点的异或和，

先树链剖分一下给每个点重新编号，然后线段树维护区间异或和

怎么维护区间异或和？对二进制的每一位建一颗线段树维护区间和(当前二进制位为1的数量)，若区间和为奇数说明这一位的区间异或结果为1，否则为0

怎么修改？

• 修改1为区间或操作：对于二进制的第\(i\)位，若\(t\)的二进制第\(i\)位为1，则会将从1到s的路径上的点权的二进制第\(i\)位全变为1，若\(t\)的二进制第\(i\)位为0，则无影响

• 修改2为区间与操作：对于二进制的第\(i\)位，若\(t\)的二进制第\(i\)位为0，则会将从1到s的路径上的点权的二进制第\(i\)位全变为0，若\(t\)的二进制第\(i\)位为1，则无影响

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int n,q;
int a[maxn];
vector<int>g[maxn];
int sz[maxn],son[maxn],f[maxn],d[maxn],top[maxn],p[maxn],tot;
struct ppo{
    int tr[maxn<<2],tag[maxn<<2];
    void clear(){memset(tag,-1,sizeof(tag));}
    void pp(int p){
        tr[p]=(tr[p<<1]+tr[p<<1|1]);
    }
    void pd(int l,int r,int p,int k){
        tr[p]=(r-l+1)*k;tag[p]=k;
    }
    void up(int dl,int dr,int l,int r,int p,int k){
        if(l>=dl&&r<=dr){
            tr[p]=(r-l+1)*k;tag[p]=k;return;
        }int mid=(l+r)>>1;
        if(~tag[p]){pd(lson,tag[p]);pd(rson,tag[p]);tag[p]=-1;}
        if(dl<=mid) up(dl,dr,lson,k);
        if(dr>mid) up(dl,dr,rson,k);
        pp(p);
    }
    int qy(int dl,int dr,int l,int r,int p){
        if(l>=dl&&r<=dr){
            return tr[p]&1;
        }int mid=(l+r)>>1;int ret=0;
        if(~tag[p]){pd(lson,tag[p]);pd(rson,tag[p]);tag[p]=-1;}
        if(dl<=mid) ret^=qy(dl,dr,lson);
        if(dr>mid) ret^=qy(dl,dr,rson);
        return ret;
    }
}seg[33];
void add(int x){
    int k=a[x];
    for(int i=0;i<=30;i++) seg[i].up(p[x],p[x],1,n,1,(k>>i)&1);
}
void dfs1(int u){
    sz[u]=1;d[u]=d[f[u]]+1;
    for(int x:g[u]){
        if(x==f[u]) continue;
        f[x]=u;dfs1(x);
        sz[u]+=sz[x];
        if(sz[x]>sz[son[u]]) son[u]=x;
    }
}
void dfs2(int u,int t){
    top[u]=t;p[u]=++tot;add(u);
    if(son[u]) dfs2(son[u],t);
    for(int x:g[u]){
        if(x==f[u]||x==son[u]) continue;
        dfs2(x,x);
    }
}
void gao(int x,int y,int s,int k){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        seg[s].up(p[top[x]],p[x],1,n,1,k);x=f[top[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    seg[s].up(p[y],p[x],1,n,1,k);
}
int cal(int x,int y,int s){
    int ret=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ret^=seg[s].qy(p[top[x]],p[x],1,n,1);
        x=f[top[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    return seg[s].qy(p[y],p[x],1,n,1)^ret;
}
int main(){
    //ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    scanf("%d%d",&n,&q);
    for(int i=0;i<=30;i++) seg[i].clear();
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=2,a,b;i<=n;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs1(1);dfs2(1,1);
    while(q--){
        int op,s,t;
        scanf("%d%d%d",&op,&s,&t);
        if(op==1){
            for(int i=0;i<=30;i++)
                if((t>>i)&1) gao(1,s,i,1);
        }else if(op==2){
            for(int i=0;i<=30;i++)
                if(!((t>>i)&1)) gao(1,s,i,0);
        }else{
            int ans=0;
            for(int i=0;i<=30;i++)
                if(cal(1,s,i)) ans|=(1<<i);
            if(ans^t) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}