出题人题解 | #筱玛的D球#

原题解链接：https://ac.nowcoder.com/discuss/151505

按位考虑。

我们可以使用树剖线段树维护所有$logVlogV$个位的信息，计算出这一位为$0\mathrm{/}10/1$时，最后的结果。复杂度$O(log2nlogV)O(log2\; n\; logV)$,难以通过此题。

我们可以将$6464$位的状态信息压在两个$unsignedlonglongunsigned\; \backslash \; long\; \backslash \; long$中，利用位运算$O(1)O(1)$维护所有位的信息。复杂度$O(log2n)O(log2\; n)$。

具体的维护我们可以使用$t_{0}t\_0$表示输入的第$ii$位为$00$时，结果为$\lfloor \frac{t_0}{2^t}\rfloor \mathrm{m}\mathrm{o}\mathrm{d}2\backslash left\backslash lfloor\backslash frac\{t\_\{0\}\}\{2^\{t\}\}\backslash right\backslash rfloor\; \backslash bmod\; 2$，$t_{1}t\_1$表示输入的第$ii$位为$11$时,结果为$\lfloor \frac{t_1}{2^i}\rfloor \mathrm{m}\mathrm{o}\mathrm{d}2\backslash left\backslash lfloor\backslash frac\{t\_\{1\}\}\{2^\{i\}\}\backslash right\backslash rfloor\; \backslash bmod\; 2$ 。

因为每一位的变换规律是独立且相同的，我们可以直接用位运算实现。

#include<algorithm>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MAXN 500010
#define BUF 1048576
typedef unsigned long long ulnt;
inline char ga(){
    char s[10];
    scanf("%s",s);
    return s[0];
}
inline int gi(){
    int x;
    scanf("%d",&x);
    return x;
}
inline ulnt gul(){
    ulnt x;
    scanf("%llu",&x);
    return x;
}
const ulnt ALL=~0ULL;
int n,m;
int head[MAXN],to[MAXN<<1],next[MAXN<<1],tot=0;
inline void $(int u,int v){next[tot]=head[u],to[tot]=v,head[u]=tot++;next[tot]=head[v],to[tot]=u,head[v]=tot++;}
int fa[MAXN],deep[MAXN],size[MAXN],dfn[MAXN],top[MAXN],nxt[MAXN],pre[MAXN],dfsclk=0;
void g(int x){
	size[x]=1;
	for(int i=head[x];~i;i=next[i]){
		if(to[i]==fa[x])continue;
		fa[to[i]]=x;pre[to[i]]=(i>>1)+1;deep[to[i]]=deep[x]+1;
		g(to[i]);
		size[x]+=size[to[i]];
	}
}
void s(int x){
	dfn[x]=++dfsclk;
	if(!top[x])top[x]=x;
	int max=0;
	for(int i=head[x];~i;i=next[i]){
		if(to[i]==fa[x]||size[to[i]]<=size[max])continue;
		max=to[i];
	}
	if(max)top[max]=top[x],s(max);
	for(int i=head[x];~i;i=next[i]){
		if(to[i]==fa[x])continue;
		if(to[i]==max)nxt[x]=(i>>1)+1;else s(to[i]);
	}
}
struct t {
	ulnt l0,l1,r0,r1;
	inline t(ulnt l0=0,ulnt l1=ALL,ulnt r0=0,ulnt r1=ALL):l0(l0),l1(l1),r0(r0),r1(r1){}
	inline t friend operator+(const t&a,const t&b){
		return t((a.l0&b.l1)|(~a.l0&b.l0),(a.l1&b.l1)|(~a.l1&b.l0),(b.r0&a.r1)|(~b.r0&a.r0),(b.r1&a.r1)|(~b.r1&a.r0));
	}
} val[MAXN<<2];
void mdf(int n,int l,int r,int p,t v){
	if(l==r)return val[n]=v,void();
	int mid=(l+r)>>1;
	p<=mid?mdf(n<<1,l,mid,p,v):mdf(n<<1|1,mid+1,r,p,v);
	val[n]=val[n<<1]+val[n<<1|1];
}
t qry(int n,int l,int r,int L,int R){
	if(l==L&&r==R)return val[n];
	int mid=(l+r)>>1;
	if(R<=mid)return qry(n<<1,l,mid,L,R);
	if(L>mid)return qry(n<<1|1,mid+1,r,L,R);
	return qry(n<<1,l,mid,L,mid)+qry(n<<1|1,mid+1,r,mid+1,R);
}
int opt[MAXN];
ulnt w[MAXN];
inline t gen(int opt,ulnt val){
	if(opt==1){
		return t(0|val,ALL|val,0|val,ALL|val);
	} else if(opt==2){
		return t(0&val,ALL&val,0&val,ALL&val);
	} else {
		return t(0^val,ALL^val,0^val,ALL^val);
	}
}
inline void set(int x){
	if(opt[x]==1){
		mdf(1,1,n,dfn[x],t(0|w[nxt[x]],ALL|w[nxt[x]],0|w[pre[x]],ALL|w[pre[x]]));
	} else if(opt[x]==2){
		mdf(1,1,n,dfn[x],t(0&w[nxt[x]],ALL&w[nxt[x]],0&w[pre[x]],ALL&w[pre[x]]));
	} else {
		mdf(1,1,n,dfn[x],t(0^w[nxt[x]],ALL^w[nxt[x]],0^w[pre[x]],ALL^w[pre[x]]));
	}
}
inline int lca(int u,int v){
	while(top[u]!=top[v]){
		if(deep[top[u]]<deep[top[v]])std::swap(u,v);
		u=fa[top[u]];
	}
	return deep[u]<deep[v]?u:v;
}
int main(){
	n=gi(),m=gi();
	memset(head,-1,sizeof(head));
	for(int i=1;i<n;i++)$(gi(),gi());
	g(1),s(1);
	for(int i=1;i<=n;i++)opt[i]=1,w[i]=0;
	for(int i=1;i<=n;i++)set(i);
	for(;m;m--){
		int op=gi();
		if(op==1){
			int u=gi(),v=gi();
			int l=lca(u,v);
			ulnt x=gul(),y=gul(),v0,v1;
			t up,down=gen(opt[v],y);
			int last=0;
			while(top[u]!=top[l]){
				if(dfn[top[u]]<dfn[u])
					up=qry(1,1,n,dfn[top[u]]+1,dfn[u])+up;
				up=gen(opt[top[u]],w[pre[top[u]]])+up;
				u=fa[top[u]];
			}
			if(dfn[u]>dfn[l])up=qry(1,1,n,dfn[l]+1,dfn[u])+up;
			while(top[v]!=top[l]){
				if(last)
					down=gen(opt[v],w[last])+down;
				if(dfn[top[v]]<dfn[v])
					down=qry(1,1,n,dfn[top[v]],dfn[v]-1)+down;
				last=pre[top[v]];
				v=fa[top[v]];
			}
			if(last)down=gen(opt[v],w[last])+down;
			if(dfn[v]>dfn[l])down=qry(1,1,n,dfn[l],dfn[v]-1)+down;
			v0=(up.r0&down.l1)|(~up.r0&down.l0);
			v1=(up.r1&down.l1)|(~up.r1&down.l0);
			ulnt now=0;
			for(int i=63;~i;i--){
				if(((v0>>i)&1)||!((v1>>i)&1)||(now+(1ULL<<i)>x))continue;
				now+=1ULL<<i;
			}
			printf("%llu\n",now);
		} else if(op==2){
			int x=gi();
			char ch=ga();
			opt[x]=ch=='x'?0:ch=='o'?1:2;set(x);
		} else if(op==3){
			int x=gi();
			ulnt v=gul();
			w[x]=v;set(to[(x-1)<<1]);set(to[(x-1)<<1|1]);
		}
	}
	return 0;
}