【bzoj2819】Nim（dfs序+树状数组/线段树）

时间：2023-03-08 19:32:45
【bzoj2819】Nim（dfs序+树状数组/线段树）

　　题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=2819

　　首先根据SG定理，可得若每堆石子数量的异或值为0，则后手必胜，反之先手必胜。于是我们就需要维护一个支持树上单点修改，树链查询异或值的数据结构。

　　首先我们可以用树链剖分解决。然而……蒟蒻我比较懒（既懒得写也懒得调），所以我们可以采取一种被用烂了的黑科技：dfs序。

　　首先我们会发现，我们可以把查询一条链拆成查询两个端点到根的链的异或值，以及lca的权值。这样一个点的权值修改，查询时只对他的子树有贡献。所以我们可以求出树的dfs序，然后把单点修改转为区间修改，把树链查询转化为单点查询。

　　然后为了代码方便，我们可以差分，把区间l~r修改转为修改l、r+1，查询单点k转化为查询1~k的异或值，就能用树状数组维护了。

　　代码：

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define ll long long

#define ull unsigned long long

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define lowbit(x) (x& -x)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define eps 1e-18

#define maxn 500010

inline ll read()

{

    ll tmp=; char c=getchar(),f=;

    for(;c<''||''<c;c=getchar())if(c=='-')f=-;

    for(;''<=c&&c<='';c=getchar())tmp=(tmp<<)+(tmp<<)+c-'';

    return tmp*f;

}

struct edge{

    int to,nxt;

}e[*maxn];

int fir[maxn],pos[maxn],l[maxn],r[maxn],val[maxn],vis[maxn],dep[maxn];

int fa[maxn][];

int bit[maxn];

int n,q,tot=,cnt=;

char op[];

void add(int x,int y){e[tot].to=y; e[tot].nxt=fir[x]; fir[x]=tot++;}

void dfs(int now)

{

    vis[now]=; l[now]=pos[now]=++cnt;

    for(int i=fir[now];~i;i=e[i].nxt)

        if(!vis[e[i].to]){

            fa[e[i].to][]=now; dep[e[i].to]=dep[now]+; dfs(e[i].to);

        }

    r[now]=cnt;

}

inline int getlca(int x,int y)

{

    if(dep[x]<dep[y]){int tmp=x; x=y; y=tmp;}

    int k=int(log(n)/log());

    for(int i=k;i>=;i--)

        if(dep[x]-(<<i)>=dep[y])x=fa[x][i];

    if(x==y)return x;

    for(int i=k;i>=;i--)

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

    return fa[x][];

}

void change(int x,int k){if(x>n)return; for(;x<=n;x+=lowbit(x))bit[x]^=k;}

int getxor(int x){int ans=; for(;x;x-=lowbit(x))ans^=bit[x]; return ans;}

int main()

{

    memset(fir,,sizeof(fir));

    int i,j;

    n=read();

    for(i=;i<=n;i++)val[i]=read();

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

        int x=read(),y=read(); add(x,y); add(y,x);

    }

    vis[]=; fa[][]=; dep[]=; dfs();

    for(j=;<<j<=n;j++)

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

            if(fa[i][j-])fa[i][j]=fa[fa[i][j-]][j-];

    q=read();

    for(i=;i<=n;i++)change(l[i],val[i]),change(r[i]+,val[i]);

    for(i=;i<=q;i++){

        scanf("%s",op);

        if(op[]=='Q'){

            int u=read(),v=read();

            int tmp=getxor(pos[u])^getxor(pos[v])^val[getlca(u,v)];

            if(tmp)printf("Yes\n"); else printf("No\n");

        }

        else{

            int u=read(),k=read();

            change(l[u],k^val[u]); change(r[u]+,k^val[u]); val[u]=k;

        }

    }

}

bzoj2819

　　虽然我用的是普通dfs，但是好像bzoj的栈空间挺大的，并不会爆。（不过还是哪天改个人工栈吧）

相关文章