P4592 [TJOI2018] 异或

题目描述

现在有一颗以 $1$ 为根节点的由 $n$ 个节点组成的树，节点从 $1$ 至 $n$ 编号。树上每个节点上都有一个权值 $v_i$。现在有 $q$ 次操作，操作如下：

• $1~x~z$：查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值。
• $2~x~y~z$：查询节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值。

输入格式

输入的第一行是两个整数，分别代表结点个数 $n$ 和询问个数 $q$。

第二行有 $n$ 个整数，第 $i$ 个整数表示点 $i$ 的的权值 $v_i$。

接下来 $n-1$ 行，每行有两个整数 $u, v$，表示存在一条连结 $u$ 和 $v$ 的边。

接下来 $q$ 行，每行首先有一个整数 $op$，代表操作类型。

• 若 $op = 1$，则一个空格后有两个整数 $x, z$，代表查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值。
• 若 $op = 2$，则一个空格后有三个整数 $x, y, z$，代表查询节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值。

输出格式

对于每一个查询，输出一行一个整数代表答案。

输入输出样例 #1

输入 #1

7 5
1 3 5 7 9 2 4
1 2
1 3
2 4
2 5
3 6
3 7
1 3 5
2 4 6 3
1 5 5
2 5 7 2
1 1 9

输出 #1

7
6
12
11
14

说明/提示

数据规模与约定

• 对于 $10\%$ 的数据，保证 $n, q \leq 10^2$；
• 对于 $20\%$ 的数据，保证 $n, q \leq 10^3$；
• 对于 $40\%$ 的数据，保证 $n, q \leq 10^4$；
• 对于 $100\%$ 的数据，保证 $2\leq n, q \leq10^5$，$1 \leq u, v, x, y \leq n$，$1 \leq op \leq 2$，$1 \leq v_i, z \lt 2^{30}$。

题解

最大异或对一般都用01trie解决，首先我们要知道什么是trie。

01trie

trie（字典树）树是一种用于实现字符串快速检索的多叉树结构。

trie 树的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符 c，就沿着当前节点的 c 字符指针，走向该指针指向的节点。

这样我们就有了每个字符串的前缀。

要使异或和最大，我们可以贪心从高位开始选。我们还知道异或运算是相同为 $0$，不相同为 $1$，所以每次尽量让当前位为 $1$。

注意到从高位开始选其实是一个前缀信息，考虑用 01trie 维护。01trie，顾名思义，就是字符指针只有 $0$ 和 $1$。我们用下面的数据举个例子：$2$，$3$，$5$

• $2 = (10)_2$，$3 = (11)_2$，$5 = (101)_2$，再按位从高到低插入：

(默认左树为0，右树为1)

            root

          0/

           ......           (省略4~30位，因为实际上插入时是从第30位开始)

        0/
          
   0/       \1

 0/   \1   0/

    0/  \1   \1
        
    (2) (3)  (5)

树上查询

01trie只能解决序列查询，我们如何把树上查询转化成链呢？

1. 先看操作1：查询节点 x 的子树

   • 我们知道字数内dfs序连续，所以预处理dfs序，再按dfs序的顺序插入

2. 再看操作2：查询节点 x 到节点 y 的简单路径

   • 首先链上的序列一定可以查询，所以可以转换成 x -> lca(x, y) 和 y -> lca(x, y)，最后取max

我们还发现一个问题，就是都是形如在 [l, r] 中选一个 k 使得 k^x 最大，这就要用可持久化trie了。

维护一个可持久化 Trie，求出 Trie 的前缀和(sum[q]=sum[p]+1，p为q父亲)。能异或不同的数位就异或不同的数位的贪心跑一遍，用前缀(sum)相减判断是否能走。

伪代码如下：

query(l, r, x)
    for i : $log(2, max{V})$ -> 0
        val = (x >> i) & 1
        if sum[son[r][v^1]] > sum[son[l-1][v^1]]
            ans += 1 << i
            r = son[r][v^1]
            l = son[l][v^1]
        else
            r = son[r][v]
            l = son[l][v]

总体代码如下：

注意要维护 $2$ 个trie

//  [TJOI2018] 异或
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 1023;
int n, m, a[N], dep[N], f[N][23], dfn[N], tot, rnk[N], siz[N];
vector<int> tr[N];

void dfs(int u, int fa) {
    dfn[u] = ++tot;
    rnk[tot] = u;
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; i <= 20; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    siz[u] = 1;
    for (int v : tr[u]) {
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    int w = dep[v] - dep[u];
    for (int i = 0; w; i++, w >>= 1)
        if (w & 1) v = f[v][i];
    if (u == v) return u;
    for (int i = 20; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}

int idx, son[N << 6][2], sum[N << 6], rt[N << 1];

void insert(int p, int q, int x) {
    for (int i = 30; i >= 0; i--) {
        int v = (x >> i) & 1;
        son[q][v ^ 1] = son[p][v ^ 1];
        son[q][v] = ++idx;
        q = son[q][v];
        p = son[p][v];
        sum[q] = sum[p] + 1;
    }
}

int query(int p, int q, int x) {
    int res = 0;
    for (int i = 30; i >= 0; i--) {
        int v = (x >> i) & 1;
        if (sum[son[q][v ^ 1]] > sum[son[p][v ^ 1]]) {
            q = son[q][v ^ 1];
            p = son[p][v ^ 1];
            res += 1 << i;
        } else {
            q = son[q][v];
            p = son[p][v];
        }
    }
    return res;
}

void build(int u, int fa) {
    rt[u + n] = ++idx;
    insert(rt[fa + n], rt[u + n], a[u]);
    for (int v : tr[u])
        if (v != fa)
            build(v, u);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs(1, 0);
    insert(0, rt[0], 0);
    for (int i = 1; i <= n; i++) {
        rt[i] = ++idx;
        insert(rt[i - 1], rt[i], a[rnk[i]]);
    }
    build(1, -n);
    f[1][0] = -n;
    for (int opt, x, y, z; m--;) {
        cin >> opt >> x >> y;
        if (opt == 1) {
            cout << query(rt[dfn[x] - 1], rt[dfn[x] + siz[x] - 1], y) << '\n';
        } else {
            cin >> z;
            int w = lca(x, y);
            int ans1 = query(rt[f[w][0] + n], rt[x + n], z);
            int ans2 = query(rt[f[w][0] + n], rt[y + n], z);
            cout << max(ans1, ans2) << '\n';
        }
    }
    return 0;
}