额……这个……嗯……为什么今天写题解这么蛋疼……
写之前想了半天是写链剖还是写LCT，最后决定写LCT……结果写了两句发现nand这个破操作不但不满足交换律，还TM不满足结合律……这TM上哪维护去
但是这是位运算啊有独立性的，所以每个点维护每一位本来是0和1，进行了这一溜操作之后变成啥，然后就可以维护了，LCT搞搞就行了
其实我看这道题之前一直以为nand是个名字……-_-
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 100010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long int n,m,k; struct data{ bool v[2][32]; data(){ } data(unsigned int x){ int i,j; for(i=0;i<2;i++){ for(j=0;j<k;j++){ v[i][j]=1^(i&((x>>j)&1)); } } } friend data operator +(data x,data y){ int i,j; data z; for(i=0;i<2;i++){ for(j=0;j<k;j++){ z.v[i][j]=y.v[x.v[i][j]][j]; } } return z; } }; data v[MAXN],vl[MAXN],vr[MAXN]; int fa[MAXN],son[MAXN][2]; int st[MAXN],tp; bool rev[MAXN]; inline bool ir(int x){ return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; } inline void cot(int x,int y,bool z){ if(x){ fa[x]=y; } if(y){ son[y][z]=x; } } inline void torev(int x){ if(!x){ return ; } swap(son[x][0],son[x][1]); swap(vl[x],vr[x]); rev[x]^=1; } inline void ud(int x){ vl[x]=vl[son[x][0]]+v[x]+vl[son[x][1]]; vr[x]=vr[son[x][1]]+v[x]+vr[son[x][0]]; } inline void pd(int x){ if(rev[x]){ torev(son[x][0]); torev(son[x][1]); rev[x]=0; } } inline void rot(int x,bool z){ int xx=fa[x],xxx=fa[xx]; cot(son[x][z],xx,z^1); if(ir(xx)){ fa[x]=xxx; }else{ cot(x,xxx,son[xxx][1]==xx); } cot(xx,x,z); ud(xx); } inline void apd(int x){ int i; st[++tp]=x; for(i=x;!ir(i);i=fa[i]){ st[++tp]=fa[i]; } for(;tp;tp--){ pd(st[tp]); } } void splay(int x){ apd(x); while(!ir(x)){ int xx=fa[x],xxx=fa[xx]; if(ir(xx)){ rot(x,son[xx][0]==x); }else{ bool z=son[xxx][0]==xx; if(son[xx][z]==x){ rot(x,z^1); rot(x,z); }else{ rot(xx,z); rot(x,z); } } } ud(x); } inline void acs(int x){ int t=0; while(x){ splay(x); son[x][1]=t; ud(x); t=x; x=fa[x]; } } inline void reboot(int x){ acs(x); splay(x); torev(x); } inline void link(int x,int y){ reboot(x); fa[x]=y; } inline void change(int x,unsigned int y){ acs(x); splay(x); v[x]=data(y); ud(x); } void ask(int x,int y){ int i; reboot(y); acs(x); splay(x); unsigned int ans=0; for(i=0;i<k;i++){ ans+=(((unsigned int)1)<<i)*vr[x].v[0][i]; } printf("%u\n",ans); } int main(){ int i,j,x,y; unsigned int z; char o[20]; scanf("%d%d%d",&n,&m,&k); for(i=0;i<2;i++){ for(j=0;j<k;j++){ v[0].v[i][j]=vl[0].v[i][j]=vr[0].v[i][j]=i; } } for(i=1;i<=n;i++){ scanf("%u",&z); v[i]=vl[i]=vr[i]=data(z); ud(i); } for(i=1;i<n;i++){ scanf("%d%d",&x,&y); link(x,y); } while(m--){ scanf("%s%d",o,&x); if(o[0]=='R'){ scanf("%u",&z); change(x,z); } if(o[0]=='Q'){ scanf("%d",&y); ask(x,y); } } return 0; } /* 3 3 3 2 7 3 1 2 2 3 Query 2 3 Replace 1 3 Query 1 1 */