【BZOJ2019】nim

你的名字 2021-03-28 14:17 434阅读 0赞

直播写题这刺激233

原题：

著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。  
为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：  
  
1.随机选两个堆v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略，如果有，vfleaking将会考虑将这些石子堆作为初始局面之一，用来坑玩家。  
2.把堆v中的石子数变为k。  
  
由于vfleaking太懒了，他懒得自己动手了。请写个程序帮帮他吧。

1≤N≤500000, 1≤Q≤500000、

丧心病狂辣鸡出题人卡dfs\_QAQ

如果不卡dfs我不到30min就A了QAQ

平时也没啥，这次是直播啊QAQ（虽然没啥人看

第一次用栈模拟dfs，写挂了好多地方……

主要就是异或满足分配率：a^b^c=a^(b^c)，所以就可以直接线段树维护，修改是单点的也不用想那么多

注意栈模拟dfs别写挂，其中关于size的处理坑了我好久，因为在标准dfs中size是儿子dfs完后直接更新当前点的size

但是用手写栈模拟的时候需要先把所有儿子都装进栈再遍历到这个儿子

这就比较蛋疼了，我脑补了一下只会先把遍历到的点存到队列里，然后逆序遍历队列把当前size贡献到father的size里（就像后缀自动姬那样

差点直播翻车，还好最后A掉了qwq

代码：

#include<iostream>
     #include<cstdio>
     #include<algorithm>
     #include<cstring>
     #include<cmath>
     using namespace std;
     int rd(){
      int z=0,mk=1;  char ch=getchar();
         while(ch<'0'||ch>'9'){
      if(ch=='-')mk=-1;  ch=getchar();}
         while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
         return z*mk;
     }
     struct ddd{
      int nxt,y;}e[1100000];  int lk[510000],ltp=0;
     inline void ist(int x,int y){  e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y;}
     int n,m,a[510000];
     int sz[510000],fth[510000],dp[510000],tp[510000],hvchd[510000];
     int dfsod[510000],rvsod[510000],odcnt=0;
     int v[2100000];
     int stck[510000],quq=0;
     int q[510000],hd=0;
     /*void dfs1(int x){
         int mx=0;  sz[x]=1;
         for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=fth[x]){
             fth[e[i].y]=x,dp[e[i].y]=dp[x]+1;  dfs1(e[i].y);
             sz[x]+=sz[e[i].y];
             if(sz[e[i].y]>mx)  mx=sz[e[i].y],hvchd[x]=e[i].y;
         }
     }*/
     void dfs1(){
         stck[quq=1]=1;  int x,mx;
         while(quq){
             x=stck[quq--];  sz[x]=1;  q[++hd]=x;
             for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=fth[x]){
                 fth[e[i].y]=x,dp[e[i].y]=dp[x]+1;  stck[++quq]=e[i].y;
             }
         }
         for(int k=hd;k;--k)  sz[fth[q[k]]]+=sz[q[k]];
         stck[quq=1]=1;
         while(quq){
             x=stck[quq--];  mx=0;
             for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=fth[x])
                 if(sz[e[i].y]>mx)  mx=sz[e[i].y],hvchd[x]=e[i].y;
             for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=fth[x])
                 stck[++quq]=e[i].y;
         }
     }
     /*void dfs2(int x){
         dfsod[++odcnt]=x,rvsod[x]=odcnt;
         if(hvchd[x])  tp[hvchd[x]]=tp[x],dfs2(hvchd[x]);
         for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=hvchd[x] && e[i].y!=fth[x])
             tp[e[i].y]=e[i].y,dfs2(e[i].y);
     }*/
     void dfs2(){
         stck[quq=1]=1;  int x;
         while(quq){
             x=stck[quq--];
             dfsod[++odcnt]=x,rvsod[x]=odcnt;
             for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=hvchd[x] && e[i].y!=fth[x])
                 tp[e[i].y]=e[i].y,stck[++quq]=e[i].y;
             if(hvchd[x])  tp[hvchd[x]]=tp[x],stck[++quq]=hvchd[x];
         }
     }
     void gtsgmttr(int x,int l,int r){
         if(l==r){  v[x]=a[dfsod[l]];  return ;}
         int md=(l+r)>>1;
         gtsgmttr(x<<1,l,md),gtsgmttr(x<<1|1,md+1,r);
         v[x]=v[x<<1]^v[x<<1|1];
     }
     void mdf(int x,int y,int z,int l,int r){
         if(y<l || y>r || l>r)  return ;
         if(l==r){  v[x]=z;  return ;}
         int md=(l+r)>>1;
         if(y<=md)  mdf(x<<1,y,z,l,md);
         else  mdf(x<<1|1,y,z,md+1,r);
         v[x]=v[x<<1]^v[x<<1|1];
     }
     int qr(int x,int l,int r,int ll,int rr){
         if(l<ll || r>rr || l>r || ll>rr)  return 0;
         if(l==ll && r==rr)  return v[x];
         int md=(ll+rr)>>1;
         if(l<=md && r>md)  return qr(x<<1,l,md,ll,md)^qr(x<<1|1,md+1,r,md+1,rr);
         else if(r<=md)  return qr(x<<1,l,r,ll,md);
         else  return qr(x<<1|1,l,r,md+1,rr);
     }
     int upupup(int x,int y){
         int bwl=0,fa=tp[x],fb=tp[y];
         while(fa!=fb){
             if(dp[fa]<dp[fb])  swap(fa,fb),swap(x,y);
             bwl^=qr(1,rvsod[fa],rvsod[x],1,n);
             x=fth[fa],fa=tp[x];
         }
         if(dp[x]>dp[y])  swap(x,y);
         //if(x!=y)  bwl^=qr(1,rvsod[x]+1,rvsod[y],1,n);
         bwl^=qr(1,rvsod[x],rvsod[y],1,n);
         return bwl;
     }
     int main(){
      //freopen("ddd.in","r",stdin);
         //freopen("ddd.out","w",stdout);
     /*int __size__ = 20 << 20; // 20MB
     char *__p__ = (char*)malloc(__size__) + __size__;
     __asm__("movl %0, %%esp\n" :: "r"(__p__));*/
         cin>>n;
         for(int i=1;i<=n;++i)  a[i]=rd();
         int l,r;  char s[2];
         for(int i=1;i<n;++i)  l=rd(),r=rd(),ist(l,r),ist(r,l);
         tp[1]=1,dfs1(),dfs2(),gtsgmttr(1,1,n);
         cin>>m;
         while(m--){
             scanf("%s",s);  l=rd(),r=rd();
             if(s[0]=='Q'){
                 if(upupup(l,r))  printf("Yes\n");
                 else  printf("No\n");
             }
             else  mdf(1,rvsod[l],r,1,n);
         }
         //cout<<clock()<<endl;
         return 0;
     }