P4592 [TJOI2018]异或

给定一棵树，每次询问一个子树的每个点与 z 的异或最大值，或者询问一条路径上每一个点和 z 的异或最大值。

同样的，这道题也可以直接树剖+ 可持久化01Trie 来解决。

但是我们可以考虑更好一点的办法：

和之前那道题一样，我们可以采用树上差分的思路，然后照常在 Trie 树上二分即可。

这里就不赘述了。

代码：

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=3e5+5,NN=1e8;
int n,m,q,a[N],root[N],cur,Idx,b[N];
int nex[N<<1],to[N<<1],head[N],idx;
int fa[N][20],dep[N],Fa[N],siz[N];
inline int Getfa(int x){return x==Fa[x]?x:Fa[x]=Getfa(Fa[x]);}
inline void add(int u,int v){
	nex[++idx]=head[u];
	to[idx]=v;
	head[u]=idx;
	return ;
}
int ch[N*32][2],sum[N*62],Cur;
void Insert(int x,int pre,int k,int v){
	if(k<0) return;
	int c=(v>>k)&1;
	ch[x][c^1]=ch[pre][c^1];
	ch[x][c]=++Cur;sum[ch[x][c]]=sum[ch[pre][c]]+1;
	Insert(ch[x][c],ch[pre][c],k-1,v);
	return ;
}
inline void Update(int x,int f){
	fa[x][0]=f;dep[x]=dep[f]+1;
	for(int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	root[x]=++Cur;
	Insert(root[x],root[f],31,a[x]);
	return ;
}
int QueryLca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=18;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	if(u==v) return u;
	for(int i=18;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int Query(int u,int v,int lca,int falca,int k,int V){
	if(k<0) return 0;
	int c=(V>>k)&1;
	if(sum[ch[u][c^1]]+sum[ch[v][c^1]]-sum[ch[lca][c^1]]-sum[ch[falca][c^1]]>0) return (1<<k)+Query(ch[u][c^1],ch[v][c^1],ch[lca][c^1],ch[falca][c^1],k-1,V);
	return Query(ch[u][c],ch[v][c],ch[lca][c],ch[falca][c],k-1,V);
}
void Build(int x,int f){
	Update(x,f);
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==f) continue;
		Build(y,x);
	}
	return ;
}
void Link(int u,int v){
	int x=Getfa(u),y=Getfa(v);
	if(siz[x]<siz[y]) swap(u,v),swap(x,y);
	siz[x]+=siz[y],Fa[y]=x;
	add(u,v),add(v,u);
	Build(v,u);
	return ;
}
int dfn[N],DFN,rev[N];
void dfs(int x,int f){
	Update(x,f);
	dfn[x]=++DFN;
	rev[DFN]=x;siz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(y==f) continue;
		dfs(y,x);
		siz[x]+=siz[y];
	}
	return ;
}
int Root[N],cur1,ch1[N*32][2],sum1[N*62];
void Insert1(int x,int pre,int k,int w){
	if(k<0) return ;
	int c=(w>>k)&1;
	ch1[x][c^1]=ch1[pre][c^1];ch1[x][c]=++cur1;sum1[ch1[x][c]]=sum1[ch1[pre][c]]+1;
	Insert1(ch1[x][c],ch1[pre][c],k-1,w);
	return ;
}
int Query1(int u,int v,int k,int w){
	if(k<0) return 0;
	int c=(w>>k)&1;
	if(sum1[ch1[v][c^1]]-sum1[ch1[u][c^1]]>0) return (1<<k)+Query1(ch1[u][c^1],ch1[v][c^1],k-1,w);
	return Query1(ch1[u][c],ch1[v][c],k-1,w);
}
int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]),Fa[i]=i,siz[i]=1;
	for(int i=1;i<=n;i++) root[i]=++Cur,Insert(root[i],0,31,a[i]);
	for(int i=1;i<n;i++){
		int u,v;
		read(u),read(v);
		add(u,v);add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=DFN;i++) Root[i]=++cur1,Insert1(Root[i],Root[i-1],31,a[rev[i]]);
	for(int i=1;i<=m;i++){
		int u,v,w,op;
		read(op);
		if(op==1){
			read(u),read(w);
			write(Query1(Root[dfn[u]-1],Root[dfn[u]+siz[u]-1],31,w)),putchar('
');
			continue;
		}
		read(u),read(v),read(w);
		int LCA=QueryLca(u,v);
		write(Query(root[u],root[v],root[LCA],root[fa[LCA][0]],31,w)),putchar('
');
	}
	return 0;
}