【[TJOI2018]异或】

写板子了，可持久化\(Trie\)的板子了

其实和主席树写法类似，还是存好左右儿子之后存好权值

之后差分去查询就好了

这道题第一问我们直接\(dfs\)序转化成区间

第二问搞成\(x,y,lca(x,y),fa[lca]\)之后一起差分就好了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 100005

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

struct E{int v,nxt;}e[maxn<<1];

int n,m,__,num,bit[35],cnt;

int rt[maxn],ch[maxn*35*2][2],v[maxn*35*2],a[maxn],Rt[maxn];

int head[maxn],top[maxn],son[maxn],sum[maxn],fa[maxn],to[maxn],_to[maxn],deep[maxn];

inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}

int change(int pre,int t) {

	int root=++cnt;

	int val=bit[t];

	v[root]=v[pre]+1;

	if(!t) return root;

	ch[root][val^1]=ch[pre][val^1];

	ch[root][val]=change(ch[pre][val],t-1);

	return root;

}

int query(int l,int r,int t) {

	if(!t) return 0;

	int val=bit[t];

	int now=v[ch[r][val^1]]-v[ch[l][val^1]];

	if(now) return (1<<(t-1))+query(ch[l][val^1],ch[r][val^1],t-1);

	return query(ch[l][val],ch[r][val],t-1);

}

int ask(int a,int b,int c,int d,int t) {

	if(!t) return 0;

	int val=bit[t];

	int now=v[ch[a][val^1]]+v[ch[b][val^1]]-v[ch[c][val^1]]-v[ch[d][val^1]];

	if(now) return (1<<(t-1))+ask(ch[a][val^1],ch[b][val^1],ch[c][val^1],ch[d][val^1],t-1);

	return ask(ch[a][val],ch[b][val],ch[c][val],ch[d][val],t-1);

}

void dfs1(int x) {

	int maxx=-1;sum[x]=1;

	for(re int i=head[x];i;i=e[i].nxt)

	if(!deep[e[i].v])

	{

		deep[e[i].v]=deep[x]+1;

		int now=0,t=a[e[i].v];

		memset(bit,0,sizeof(bit));

		while(t) bit[++now]=(t&1),t>>=1;

		Rt[e[i].v]=change(Rt[x],32);

		fa[e[i].v]=x;dfs1(e[i].v);

		sum[x]+=sum[e[i].v];

		if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;

	}

}

void dfs2(int x,int topf) {

	top[x]=topf;to[++__]=x;_to[x]=__;

	if(!son[x]) return;

	dfs2(son[x],topf);

	for(re int i=head[x];i;i=e[i].nxt) if(!top[e[i].v]) dfs2(e[i].v,e[i].v);

}

inline int LCA(int x,int y) {

	while(top[x]!=top[y])

	{if(deep[top[x]]<deep[top[y]]) std::swap(x,y); x=fa[top[x]];}

	if(deep[x]<deep[y]) return x;return y;

}

int main()

{

	n=read(),m=read();

	for(re int i=1;i<=n;i++) a[i]=read();

	int x,y,opt,val;

	for(re int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);

	deep[1]=1,dfs1(1),dfs2(1,1);

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

	{

		int now=0,t=a[to[i]];

		memset(bit,0,sizeof(bit));

		while(t) bit[++now]=(t&1),t>>=1;

		rt[i]=change(rt[i-1],32);

	}

	while(m--)

	{

		opt=read();x=read();

		if(opt==1) val=read();

		if(opt==2) y=read(),val=read();

		int now=0;

		memset(bit,0,sizeof(bit));

		while(val) bit[++now]=(val&1),val>>=1;

		if(opt==1) printf("%d\n",query(rt[_to[x]-1],rt[_to[x]+sum[x]-1],32));

		if(opt==2) {int lca=LCA(x,y);printf("%d\n",ask(Rt[x],Rt[y],Rt[lca],Rt[fa[lca]],32));}

	}

	return 0;

}

巴特西

【[TJOI2018]异或】

最新文章

热门文章