「BZOJ 3261」最大异或和

Description

给定一个非负整数序列 $\{a\}$，初始长度为 $N$ 。

有 $M$ 个操作，有以下两种操作类型：

A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N+1$ 。

Q l r x：询问操作，你需要找到一个位置 $p$，满足 $l \le p \le r$，使得 $a_p \oplus a_{p+1} \oplus \cdots \oplus a_N \oplus x$ 最大，输出最大是多少。

$(1 \leq N,M \leq 3 \times 10^5,0 \leq a_i \leq 10^7)$

Source

[BZOJ]3261

Solution

先考虑简化问题。

我们可以像前缀和一样预处理出 $pre_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i$，再根据异或运算的性质，可以得到：

$$a_l \oplus a_{l + 1} \oplus \cdots \oplus a_{r - 1} \oplus a_r = pre_{r} \oplus pre_{l - 1}$$

问题就变为找到一个位置 $p - 1$，满足 $l - 1 \le p - 1 \le r - 1$，使得 $pre_n \oplus pre_{p - 1} \oplus x$ 最大。显然 $pre_n$ 和 $x$ 都已知，所以我们只需要找与 $x \oplus pre_n$ 在指定范围内且异或结果最大的 $pre_{p - 1}$ 即可。

看到这个问题，很容易想到用 0-1 Trie 来维护。但是因为限制了区间，一棵 Trie 是肯定不够用的，所以还要 可持久化 。

可持久化 Trie 和 主席树 的实现方法相似。我们每插入一个前缀异或和 $pre_i$，就建一棵 Trie 。由于第 $i$ 棵 Trie 与第 $i - 1$ 棵 Trie 最多只会有 $\log n$ 棵节点是不同的。所以插入时，我们只需要新建一个根，只对当前数的每一位新建节点，其余的点连向上一棵树。这样空间复杂度可以优化为 $O(n \log n)$ 。在上述插入的过程中，我们只需要记录第 $i$ 棵 Trie 每个节点的个数，就能判断一个区间内是否有该节点。查询也很容易，从第 $l - 2$ 与第 $r - 1$ 棵 Trie 的根开始（因为这两棵 Trie 之间的数为 $pre_{l - 1} \sim pre_{r - 1}$），判断是否存在与 $x$ 某一位取反的节点，具体过程类似 [LOJ]10050 。不要忘记在第 $0$ 棵 Trie 上插入 $0$，时间复杂度为 $O(n \log n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

inline void readChar(char &c) {
    for (c = getchar(); c != 'A' && c != 'Q'; c = getchar());
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 6e5;
int n, m, pre[MAXN + 5];
struct Trie {
    int tot, root[MAXN + 5], sum[MAXN * 23 + 5], ch[MAXN * 23 + 5][2];
    
    inline void update(int &rt, int pre, int x) {
        rt = ++tot;//建一个新的根 
        int u = rt;//当前节点 
        for (int i = 23; ~i; --i) {
            bool v = x & (1 << i);
            ch[u][v] = ++tot, ch[u][v ^ 1] = ch[pre][v ^ 1];
            //对当前数新建节点，另一分支连向上一棵树
            u = ch[u][v], pre = ch[pre][v];//向下一层走 
            sum[u] = sum[pre] + 1;//记录该节点个数 
        }
    }
    inline int query(int ql, int qr, int x) {
        int res = 0;
        for (int i = 23; ~i; --i) {
            bool v = x & (1 << i);
            if (ch[ql][v ^ 1] < ch[qr][v ^ 1]) {//存在相反的节点 
                res += 1 << i;//异或后第 i 位上是 1 
                ql = ch[ql][v ^ 1], qr = ch[qr][v ^ 1];
            } else ql = ch[ql][v], qr = ch[qr][v];//同时向下一层走 
        }
        return res;
    }
} tr;

int main() {
    read(n), read(m);
    tr.update(tr.root[0], 0, 0);//在第 0 棵 Trie 中插入 0 
    for (int x, i = 1; i <= n; ++i) {
        read(x);
        pre[i] = pre[i - 1] ^ x;//前缀异或和
        tr.update(tr.root[i], tr.root[i - 1], pre[i]);//在上一棵 Trie 的基础上插入 pre[i] 
    }
    for (int l, r, x, i = 1; i <= m; ++i) {
        char opt;
        readChar(opt);
        if (opt == 'A') {
            read(x);
            ++n;
            pre[n] = pre[n - 1] ^ x;//更新前缀异或和 
            tr.update(tr.root[n], tr.root[n - 1], pre[n]);//插入新数 
        } else {
            read(l), read(r), read(x);
            if (l == 1) write(tr.query(0, tr.root[r - 1], x ^ pre[n]));
            //l = 1 时，要把 p = 1 的情况算进去，也就是说 Trie 中还要有 0 这个数，
            //因为 x ^ pre[n] 可能是最大的
            else write(tr.query(tr.root[l - 2], tr.root[r - 1], x ^ pre[n]));
            //区间为 [l - 1, r - 1]，所以起始的根应该为 l - 2 和 r - 1 
            putchar('\n');
        }
    }
    return 0;
}