题解 P4592 【[TJOI2018]异或】

· · 题解

题意

给一棵 n 个点的树，每个点有点权。有 q 次操作，每次操作为查询链上或子树中点权与 x 异或的最大值。

\texttt{Data Range:}1\leq n,q\leq 10^5

题解

不会数据结构的大彩笔居然不看题解 1A 了这题，感动……

首先这种题目应该是 01trie 求最大异或和。由于处理子树询问的时候对每个点都开一个 01trie 显然不现实，所以考虑可持久化 01trie。

首先考虑所有的子树内询问。因为可持久化 01trie 本质上是高度为 32 的主席树，具有可减性，所以如果把这个东西拍到序列上会非常好做。于是用 dfs 序将一个子树内的东西拍到一段连续的区间上，然后类似区间 k 小值就做完了。

对于所有的链上询问，可以参考 Count on a tree 那题的做法，也就是一个节点上的可持久化 01trie 上有这个节点到根路径上所有数，对于查询的话直接树上差分就好了。因为这东西具有可减性所以没什么问题。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51;
struct Edge{
    ll to,prev;
};
Edge ed[MAXN<<1];
ll n,qcnt,op,u,v,c,tot,totn,totd;
ll x[MAXN],last[MAXN],rt[MAXN],rt2[MAXN],dfn[MAXN],sz[MAXN];
ll fa[MAXN],depth[MAXN],rdfn[MAXN],hv[MAXN],top[MAXN],s[MAXN<<6];
ll ch[MAXN<<6][2];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void addEdge(ll from,ll to)
{
    ed[++tot].prev=last[from];
    ed[tot].to=to;
    last[from]=tot;
}
inline ll insert(ll x,ll node,ll depth) 
{
    ll cur=++totn;
    s[cur]=s[node]+1,ch[cur][0]=ch[node][0],ch[cur][1]=ch[node][1];
    if(depth==-1)
    {
        return cur;
    }
    return ch[cur][(x>>depth)&1]=insert(x,ch[node][(x>>depth)&1],depth-1),cur;
}
inline void dfs(ll node,ll f)
{
    ll mx=-1;
    rdfn[dfn[node]=++totd]=node,sz[node]=1,depth[node]=depth[f]+1;
    rt2[node]=insert(x[node],rt2[fa[node]=f],31);
    for(register int i=last[node];i;i=ed[i].prev)
    {
        if(ed[i].to!=f)
        {
            dfs(ed[i].to,node),sz[node]+=sz[ed[i].to];
            sz[ed[i].to]>mx?mx=sz[hv[node]=ed[i].to]:1;
        }
    }
}
inline void dfs2(ll node,ll link)
{
    ll to;
    top[node]=link;
    if(!hv[node])
    {
        return;
    }
    dfs2(hv[node],link);
    for(register int i=last[node];i;i=ed[i].prev)
    {
        (to=ed[i].to)!=fa[node]&&to!=hv[node]?dfs2(to,to):(void)1;
    }
}
inline ll LCA(ll x,ll y)
{
    while(top[x]!=top[y])
    {
        depth[top[x]]<depth[top[y]]?swap(x,y):(void)1,x=fa[top[x]];
    }
    return depth[x]<depth[y]?x:y;
}
inline ll query(ll x,ll lc,ll rc,ll depth)
{
    if(depth==-1)
    {
        return 0;
    }
    ll nxt=!((x>>depth)&1),d=nxt^(!(s[ch[rc][nxt]]-s[ch[lc][nxt]]));
    return (d<<depth)+query(x,ch[lc][d],ch[rc][d],depth-1);
}
inline ll query(ll x,ll l1,ll l2,ll l3,ll l4,ll depth)
{
    if(depth==-1)
    {
        return 0;
    }
    ll nxt=!((x>>depth)&1);
    ll d=nxt^(!(s[ch[l1][nxt]]+s[ch[l2][nxt]]-s[ch[l3][nxt]]-s[ch[l4][nxt]]));
    return (d<<depth)+query(x,ch[l1][d],ch[l2][d],ch[l3][d],ch[l4][d],depth-1);
}
inline ll query(ll u,ll v,ll x)
{
    ll l=LCA(u,v);
    return query(x,rt2[u],rt2[v],rt2[l],rt2[fa[l]],31);
}
int main()
{
    n=read(),qcnt=read();
    for(register int i=1;i<=n;i++)
    {
        x[i]=read();
    }
    for(register int i=0;i<n-1;i++)
    {
        u=read(),v=read(),addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0),dfs2(1,1);
    for(register int i=1;i<=n;i++)
    {
        rt[i]=insert(x[rdfn[i]],rt[i-1],31);
    }
    for(register int i=1;i<=qcnt;i++)
    {
        op=read();
        if(op==1)
        {
            u=read(),c=read();
            printf("%d\n",query(c,rt[dfn[u]-1],rt[dfn[u]+sz[u]-1],31)^c);
        }
        if(op==2)
        {
            u=read(),v=read(),c=read(),printf("%d\n",query(u,v,c)^c);
        }
    }
}