题解 P7242 [COCI2019-2020#4] Klasika

硫酸 · 2023-11-04 17:52:00 · 题解

update on 11.6

添加了解法二，并修改了解法一的小部分内容。

解法一

算是对 @MuelsyseU 的做法的补充吧。

先是一个比较套路的转化：记点 u 到根的异或路径为 dis_u，则 a,b 间的异或路径就是 dis_a \oplus dis_b，那么 Query u v 的答案就是 \max\limits_{x \in subtree_v } \{ dis_u \oplus dis_x\}。

如果对于一个点 v，将它子树内所有点的 dis 放到一棵 01-trie 上。询问时在 01-trie 从根向叶子走，对于每一位尽可能往 dis_u 相反的方向上走就行了。这一部分也可以参考 P4551 最长异或路径。

问题在于怎么求出每个点的 01-trie 。

考虑树上启发式合并。对于点 u，先处理掉所有儿子的 01-trie ，再将重儿子的 01-trie 直接转移到点 u 上，然后把所有轻儿子的 01-trie 合并到 u 上面。

关于复杂度，只有当一个点是轻儿子才会合并。而一条链最多包含 \log n 条重链，于是每个数最多只会添加（包括合并次数）到 01-trie 里 \log n 次，n 个点就是 n\log n 次。每次查询只要在 01-trie 里从根到叶子走一次，也是 \log n。

总复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    template<typename T>inline void read(T &x)
    {
        x=0;int y=1;
        char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
        while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
        x*=y;
        return;
    }
    template<typename T>inline void write(T x)
    {
        if(x<0){putchar('-');x=-x;}
        if(x>9) write(x/10);
        putchar(x%10 + '0');
        return;
    }
}
using namespace IO;
#define writeln(x) write(x),putchar('\n')
#define writesp(x) write(x),putchar(' ')
#define debug printf("Now is on line %d\n",__LINE__)
const int N=2e5+5;
int n=1,Q,tot=0,ans,fa[N],a[N],rt[N],siz[N],hson[N];//rt为每个点上01-trie的根，hson为重儿子
struct Que{int u,v,tim,ans;}inp[N];//离线操作
struct dot{int tim,son[2];}f[N*30];//01-trie
vector<int> w[N],que[N];//w存图，que存每个节点上的询问
int New(int tim)
{
    ++tot;f[tot].tim=tim;f[tot].son[0]=0;f[tot].son[1]=0;
    return tot;
}
void add(int id,int x,int dep,int tim)//向01-trie里加入一个数
{
    f[id].tim=min(f[id].tim,tim);
    if(dep<0) return;
    int op=((x>>dep)&1);
    if(!f[id].son[op]) f[id].son[op]=New(tim);
    add(f[id].son[op],x,dep-1,tim);
    return;
}
void merge(int id,int id2,int dep)//合并两个01-trie
{
    if(!id2) return;
    f[id].tim=min(f[id].tim,f[id2].tim);
    if(dep<0) return;
    if(!f[id].son[0]) f[id].son[0]=f[id2].son[0];
    else merge(f[id].son[0],f[id2].son[0],dep-1);
    if(!f[id].son[1]) f[id].son[1]=f[id2].son[1];
    else merge(f[id].son[1],f[id2].son[1],dep-1);
    return;
}
void query(int id,int x,int dep,int tim)//在01-trie里查询
{
    int op=(((x>>dep)&1)^1);//找到数字x第dep位，取反（尽可能往相反方向走）
    if(!f[id].son[op] || f[f[id].son[op]].tim>tim) op^=1;
    ans|=(op<<dep);
    if(dep) query(f[id].son[op],x,dep-1,tim);
    return;
}
void dfs(int id)
{
    siz[id]=1;hson[id]=0;
    for(int to : w[id])
    {
        dfs(to);
        siz[id]+=siz[to];
        if(siz[hson[id]]<siz[to]) hson[id]=to;
    }
    if(hson[id]) swap(rt[id],rt[hson[id]]);//将重儿子（如果有）的01-trie直接转移到当前点
    for(int to : w[id]) merge(rt[id],rt[to],30);//合并其他轻儿子
    for(int i : que[id])
    {
        ans=0;query(rt[id],a[inp[i].u],30,i);
        inp[i].ans=(ans^a[inp[i].u]);
    }
    return;
}
signed main()
{
    int u,v;
    char cc[10];
    rt[1]=New(0);add(rt[1],0,30,0);//细节：初始要在1节点插入一个0，实际意义为走到1节点
    read(Q);
    for(int i=1;i<=Q;++i)
    {
        scanf("%s",cc);read(u);read(v);
        if(cc[0]=='A')
        {
            ++n;
            a[n]=(a[u]^v);
            fa[n]=u;
            w[u].emplace_back(n);
            rt[n]=New(i);
            add(rt[n],a[n],30,i);
        }
        else
        {
            inp[i]=Que{u,v,i,0};
            que[v].emplace_back(i);
        }
    }
    dfs(1);
    for(int i=1;i<=Q;++i) if(inp[i].tim) writeln(inp[i].ans);
    return 0;
}

解法二

来自 @gty314159 ，已在线下得到其授权。

依然离线，求出 dfs 序，将子树上的查询转化为区间查询。

先开一个数组 d，d_i 表示 dfn_u=i 的节点 u 的 dis_u。（dis 定义同上）。初始 d_i=0，按照操作顺序加入、查询。这样当一个点未加入时，查询到它等价于查询到子树的根，不影响。

然后用树套树维护这个数组 d。树状数组套 01-trie，树状数组上第 i 个 01-tire 上存储 d_1\thicksim d_i。其中 01-trie 每个节点还要记录这一位出现的次数 siz。

查询时，对于 d_l\thicksim d_r ，记第 r 棵 01-tire 和第 l-1 棵“作差”。由于第 r 棵一定是包含第 l-1 棵的，于是将第 r 棵每个节点的 siz 与第 l-1 棵作差，如果为零就是这个点在 d_l\thicksim d_r 中不存在。

作差后得到 d_l\thicksim d_r 的 01-trie ，按解法一中的查询，从根节点走一次就行了。

但是空间很紧，树状数组勉强能在 400MB 混过去，线段树会炸。

代码不是一个人写的，码风不同。

#include <bits/stdc++.h>

#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int N = 2e5 + 5;
const int K = 30;

int n = 1, m, dis[N];
vector<int> e[N];
void Addedge(int u, int v) {
    e[u].push_back(v);
    return ;
}

int cnt, dfn[N], siz[N];
void Dfs(int u) {
    dfn[u] = ++cnt;
    siz[u] = 1;
    for (auto v : e[u])
        Dfs(v), siz[u] += siz[v];
    return ;
}

int tot, rt[N], s[K + 5];
struct Trie { int s[2], siz; } t[N * 200];
void Init(int k) {
    dF(i, K, 1) s[i] = k & 1, k >>= 1;
    return ;
}
void Update(int x, int &rt) {
    Init(x);
    if (!rt) rt = ++tot;
    int u = rt;
    F(i, 1, K) {
        ++t[u].siz;
        if (!t[u].s[s[i]])
            t[u].s[s[i]] = ++tot;
        u = t[u].s[s[i]];
    }
    ++t[u].siz;
    return ;
}

int lowbit(int x) { return x & -x; }
void Update(int x) {
    for (int i = dfn[x]; i <= n; i += lowbit(i))
        Update(dis[x], rt[i]);
    return ;
}
int numl, invl[K], numr, invr[K];
void Init(int l, int r) {
    numl = numr = 0;
    for (int i = r; i; i -= lowbit(i))
        invr[++numr] = rt[i];
    for (int i = l - 1; i; i -= lowbit(i))
        invl[++numl] = rt[i];
    return ;
}
int Query(int l, int r, int x) {
    Init(l, r);
    Init(x);
    int res = 0;
    F(i, 1, K) {
        res <<= 1;
        int sum = 0;//这里把01-trie作差与查询放在一个函数里了
        F(j, 1, numr) sum += t[t[invr[j]].s[s[i] ^ 1]].siz;
        F(j, 1, numl) sum -= t[t[invl[j]].s[s[i] ^ 1]].siz;
        if (sum) {
            res ^= 1;
            F(j, 1, numr) invr[j] = t[invr[j]].s[s[i] ^ 1];
            F(j, 1, numl) invl[j] = t[invl[j]].s[s[i] ^ 1];
        } else {
            F(j, 1, numr) invr[j] = t[invr[j]].s[s[i]];
            F(j, 1, numl) invl[j] = t[invl[j]].s[s[i]];
        }
    }
    return res;
}

string op[N];
int x[N], y[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> m;
    F(i, 1, m) {
        cin >> op[i] >> x[i] >> y[i];
        if (op[i] == "Add")
            Addedge(x[i], ++n),
            dis[n] = dis[x[i]] ^ y[i];
    }
    Dfs(1);
    Update(1);
    int now = 1;
    F(i, 1, m)
        if (op[i] == "Add") Update(++now);
        else cout << Query(dfn[y[i]], dfn[y[i]] + siz[y[i]] - 1, dis[x[i]]) << "\n";
    return 0;
}