可持久化01Trie树+LCA【p4592】[TJOI2018]异或

表示不太会可持久化\(01Trie\)

参考着题解码了出来,还是有点不懂.

但是又感觉懂得差不多。

这个题差不多可以自己码出来,很好的一个题。

可持久化\(01Trie\)思想还行,类似于主席树思想.

用到了\(lastroot\).

对于现在的自己,不太想深究具体构造,感觉网上讲解的这个不是很好。

打算活过\(NOIP\)之后写一篇讲解。

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

const int maxn= 1e5+8;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

struct Trie

{

	int root[maxn],ch[maxn*35][2],tot,cnt[maxn*35];

	Trie(){root[0]=tot=1;}

	inline void insert(int lastroot,int &nowroot,int x)

	{

		nowroot=++tot;

		int u=nowroot;

		for(R int i=30;~i;i--)

		{

			R int bit=(x>>i)&1;

			ch[u][!bit]=ch[lastroot][!bit];

			ch[u][bit]=++tot;

			u=ch[u][bit];

			lastroot=ch[lastroot][bit];

			cnt[u]=cnt[lastroot]+1;

		}

	}

	inline int query(int l,int r,int x)

	{

		int res=0;

		for(R int i=30;~i;i--)

		{

			R int bit=(x>>i)&1;

			if(cnt[ch[r][!bit]]-cnt[ch[l][!bit]])

			{

				r=ch[r][!bit];

				l=ch[l][!bit];

				res+=(1<<i);

			}

			else

			{

				r=ch[r][bit];

				l=ch[l][bit];

			}

		}

		return res;

	}

}tr,se;

int dfn[maxn],fdfn[maxn],val[maxn],idx,depth[maxn];

int head[maxn],tot,l[maxn],r[maxn],size[maxn];

struct cod{int u,v;}edge[maxn<<1];

inline void add(R int x,R int y)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	head[x]=tot;

}

int f[maxn][21];

void dfs(R int u,R int fa)

{

	tr.insert(tr.root[fa],tr.root[u],val[u]);

	f[u][0]=fa;depth[u]=depth[fa]+1;

	dfn[u]=++idx,fdfn[idx]=u;size[u]=1;

	for(R int i=1;(1<<i)<=depth[u];i++)

		f[u][i]=f[f[u][i-1]][i-1];

	for(R int i=head[u];i;i=edge[i].u)

	{

		if(edge[i].v==fa)continue;

		dfs(edge[i].v,u);

		size[u]+=size[edge[i].v];

	}

}

inline int lca(R int x,R int y)

{

	if(depth[x]>depth[y])swap(x,y);

	for(R int i=17;~i;i--)

		if(depth[x]+(1<<i)<=depth[y])

			y=f[y][i];

	if(x==y)return y;

	for(R int i=17;~i;i--)

	{

		if(f[x][i]==f[y][i])continue;

		x=f[x][i],y=f[y][i];

	}

	return f[x][0];

}

int n,q;

int main()

{

	in(n),in(q);

	for(R int i=1;i<=n;i++)in(val[i]);

	for(R int i=1,x,y;i<n;i++)

	{

		in(x),in(y);

		add(x,y),add(y,x);

	}

	dfs(1,0);

	for(R int i=1;i<=n;i++)

		se.insert(se.root[i-1],se.root[i],val[fdfn[i]]);

	for(R int opt,x,y,z;q;q--)

	{

		in(opt);

		if(opt==1)

		{

			in(x),in(y);

			printf("%d\n",se.query(se.root[dfn[x]-1],se.root[dfn[x]+size[x]-1],y));

		}

		else

		{

			in(x),in(y),in(z);

			int la=lca(x,y);

			printf("%d\n",max(tr.query(tr.root[f[la][0]],tr.root[x],z),tr.query(tr.root[f[la][0]],tr.root[y],z)));

		}

	}

}