[TJOI2018]异或

可持久化Trie 树链剖分

题面

有一棵带点权的大小为$n$的树。有$Q$次操作：

• 查询某棵子树点权与$y$异或和最大值
• 查询某路径上点权与$z$异或和最大值

$n,Q\leq10^5,a_i\leq2^{30}$

解析

这似乎是可持久化$Trie$树模板和链剖模板二合一。
用链剖像维护线段树一般维护$Trie$树即可。
然后因sum空间开小调了一个小时

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
struct Edge{int to,nxt;}e[N<<1];
int h[N],cnt,n,Q,w[N],d[N],f[N],sz[N],top[N],tim,L[N],R[N],son[N],rt[N*50],tot,id[N],pzy,t[N*50][2];
ll sum[N*50];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs1(re int u,re int fa)
{
  d[u]=d[fa]+1;sz[u]=1;f[u]=fa;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs1(v,u);
      sz[u]+=sz[v];
      if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  top[u]=up;L[u]=++tim;id[tim]=u;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
  R[u]=tim;
}
il void Build(re int x,re int &y,re int w,re int dep)
{
  sum[y=++pzy]=sum[x]+1;
  if(dep<0) return;
  re int p=(w>>dep)&1;
  t[y][p^1]=t[x][p^1];
  Build(t[x][p],t[y][p],w,dep-1);
}
il int Query(re int x,re int y,re int w,re int dep)
{
  if(dep<0) return 0;
  re int p=(w>>dep)&1,tmp=sum[t[y][p^1]]-sum[t[x][p^1]];
  if(tmp>0) return (1<<dep)+Query(t[x][p^1],t[y][p^1],w,dep-1);
  else return Query(t[x][p],t[y][p],w,dep-1);
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();Q=gi();
  fp(i,1,n) w[i]=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);
    }
  dfs1(1,0);dfs2(1,1);
  fp(i,1,n) Build(rt[i-1],rt[i],w[id[i]],30);
  while(Q--)
    {
      re int op=gi(),u=gi(),v=gi(),w,ans=0;
      if(op==1) printf("%d\n",Query(rt[L[u]-1],rt[R[u]],v,30));
      else
    {
      w=gi();
      while(top[u]^top[v])
          {
            if(d[top[u]]<d[top[v]]) swap(u,v);
        ans=max(ans,Query(rt[L[top[u]]-1],rt[L[u]],w,30));//前面要rt
            u=f[top[u]];
      }
      if(d[u]<d[v]) swap(u,v);
      ans=max(ans,Query(rt[L[v]-1],rt[L[u]],w,30));
      printf("%d\n",ans);
    }
    }
  return 0;
}