CF840E In a Trap

题意

有一颗以1为根的树，每个点上有一个点权ai，每次询问路径u到v上最大的 $ai \bigoplus dist(i,v) $，保证u为v的祖先

题解

有意思的题，之前考过一道类似的，那题场切了，这题不会。

首先我们将值域折半，将 $dis$ 产生的影响分成前 $8$ 位和后 $8$ 位。
对于每个点，向上每 $256$ 块一个点，也就是说对于每一块内 $dis$ 的值前 $8$ 位不变，后 $8$ 位会变。

考虑整块的答案如何快速求，首先我们对于第 $i$ 块中某个位置 $x$ 的贡献是这样的 $f(x,v) = dis(x,k)\oplus a_x\oplus(256i) $ 其中 $k$ 是块头。

我们对于每一个 $i$ 作为块头进行处理，我们将块中元素 $a_j=>a_j\oplus t$，$t$ 是 $a_j$ 在块中的位置。
我们考虑这个块作为第 $k$ 个块时的贡献，我们将修改后的数全部插入一个 01trie，这样就相当于在 01trie中查 $256k$ 能异或出的最大值。

但是这样空间有点炸，可以卡一下空间，只插入前 $8$ 位，找到前 $8$ 位后最大值后找到这个前 $8$ 位最大的后 $8$ 位拼上。

但是还不行，直接用 $f_{i,x}$ 表示 $x$ 作为块头的块是第 $i$ 个块的最大值，在预处理 $f$ 数组时重复用 01trie 就好了。
最后整块暴力跳，散块暴力即可，时间复杂度 $O(n\sqrt{n}logn+q\sqrt{n}logn)$。

点击查看代码

#include <bits/stdc++.h>
#define pii pair<int,int>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int f(0) ; rg char c(gc()) ;
    while(!isdigit(c)) f |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (f?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; space ;
    print(p...) ;
}
bool S_GND ;
const int N = 5e4+5 ;
const int B = 256 ;
int n,Q,top ;
int pos[N],st[N] ;
int a[N],fa[N],f[B][N],dep[N],ans[N*10],mx[B] ;
vector<int>e[N] ;
vector<pii>q[N] ;
int cmp(pii x,pii y) {return dep[x.first] > dep[y.first] ;}
struct Trie
{
    int tr[B*10][2],top = 1 ;
    Trie(){me(tr,0) ;}
    void clear() {top = 1,tr[1][0] = tr[1][1] = 0 ;}
    void Insert(int x)
    {
        int p = 1 ;
        ROF(i,8,0,1)
        {
            int pos = (x>>i)&1 ;
            if(!tr[p][pos]) tr[p][pos] = ++top,tr[top][0] = tr[top][1] = 0 ; 
            p = tr[p][pos] ;
        }
    }
    int Query(int x)
    {
        int res = 0,p = 1 ;
        ROF(i,8,0,1)
        {
            int pos = (x>>i)&1 ;
            if(!tr[p][0] && !tr[p][1]) break ;
            if(tr[p][!pos]) p = tr[p][!pos],res |= 1<<i ;
            else p = tr[p][pos] ;
        }
        return res ;
    }
}g ;
void Dfs(int x)
{
    if(dep[x] >= B)
    {
        int T = B,tot = 0,now = x ; g.clear(),me(mx,0) ;
        while(T--) g.Insert(a[now]>>8),mx[a[now]>>8] = max(mx[a[now]>>8],(a[now]&255)^tot),++tot,now = fa[now] ;
        FOR(i,0,B-1,1)
        {
            int res = g.Query(i) ;
            f[i][x] = (res<<8)+mx[i^res] ; 
        }
    }
    for(auto v:e[x]) if(v != fa[x])
        fa[v] = x,dep[v] = dep[x]+1,Dfs(v) ;
}
int Get(int x)
{
    return st[pos[x]-B] ;
}
void Solve(int x)
{
    int res = 0,tot = 0,now = x ;
    st[++top] = x,pos[x] = top,sort(q[x].begin(),q[x].end(),cmp) ;
    for(auto [v,id]:q[x])
    {
        while(dep[now] > B && dep[Get(now)] > dep[v]) res = max(res,f[tot][now]),++tot,now = Get(now) ; //assert(tot < B)
        int gkd = now,p = 0 ; while(gkd != v) ans[id] = max(ans[id],(p+tot*B)^a[gkd]),++p,gkd = fa[gkd] ; ans[id] = max({ans[id],res,(p+tot*B)^a[gkd]}) ;
    }
    for(auto v:e[x]) if(v != fa[x]) Solve(v) ; --top ;
}
signed main()
{
// cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
//	freopen(".in","r",stdin) ;
//	freopen(".out","w",stdout) ;
    read(n,Q) ;
    FOR(i,1,n,1) read(a[i]) ;
    FOR(i,2,n,1)
    {
        int u,v ; read(u,v) ;
        e[u].pb(v),e[v].pb(u) ;
    }
    FOR(i,1,Q,1)
    {
        int u,v ; read(u,v) ;
        q[v].pb({u,i}) ;
    }
    Dfs(1),Solve(1) ; 
    FOR(i,1,Q,1) print(ans[i]),enter ;
    return 0 ;
}

JZTXT

CF840E In a Trap

CF840E In a Trap

题意

题解