题目链接：HDU 6579

给定一个长度为 $n$ 的序列 $a$，接下来有 $m$ 个操作，操作分为如下 $2$ 种：

• 0 l r：选择 $a_l, a_{l +1}, \dots, a_{r}$ 中的一些数，使得他们的异或和最大，输出最大的异或和。
• 1 x：将 $x$ 加入到序列的最后，并且将 $n$ 更新为 $n + 1$。

操作强制在线，我们设 $lastans$ 表示上一次操作 $0$ 的答案，初始值为 $0$。

对于所有操作 $0$，令 $l = (l\ \text{xor}\ lastans) \bmod n +1$，$r = (r\ \text{xor}\ lastans)\bmod n +1$，如果 $l > r$ 则交换两数。

对于所有操作 $1$，令 $x = x\ \text{xor}\ lastans$。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n, m \le 5 \times 10 ^ 5$，$\sum n, \sum m \le 10 ^ 6$，$0 \le a_i, x < 2 ^ {30}$。

Solution

Orz 会线段树维护线性基的 hehezhou

因为只有插入操作，因此不需要动态维护线性基，只需要维护「前缀的线性基」即可。

对于每个线性基，将出现位置靠右的数字尽可能地放在高位，如果某个位置上的新数字比原数字的位置更换靠右，则将原数字推向低位，而将新数字放在当前位置上。

求最大异或和时，只需要贪心地将前缀 $r$ 的线性基中的数加入答案。

时间复杂度：$\mathcal O(T(n + m) \log w)$，$w$ 为序列的值域。

Code

#include <cstdio>
#include <algorithm>

const int N = 5e5 + 5, M = 30;

int T, n, m;

struct Base {
    int r[M], p[M];
    void insert(int v, int x) {
        for (int i = 29; i >= 0; i--) {
            if ((v & (1 << i)) == 0) continue;
            if (r[i] > 0) {
                if (x > p[i]) {
                    std::swap(v, r[i]);
                    std::swap(x, p[i]);
                }
                v ^= r[i];
            } else {
                r[i] = v;
                p[i] = x;
                break;
            }
        }
    }
    int query(int l) {
        int ans = 0;
        for (int i = 29; i >= 0; i--) {
            if (p[i] >= l && (ans ^ r[i]) > ans) ans ^= r[i];
        }
        return ans;
    }
} pre[N];

int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%d%d", &n, &m);
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            pre[i] = pre[i - 1];
            pre[i].insert(x, i);
        }
        for (int i = 1, lastans = 0, opt; i <= m; i++) {
            scanf("%d", &opt);
            if (opt == 0) {
                int l, r;
                scanf("%d%d", &l, &r);
                l = (l ^ lastans) % n + 1;
                r = (r ^ lastans) % n + 1;
                if (l > r) std::swap(l, r);
                printf("%d\n", lastans = pre[r].query(l));
            } else {
                int x;
                scanf("%d", &x);
                pre[n + 1] = pre[n], n++;
                pre[n].insert(x ^ lastans, n);
            }
        }
    }
    return 0;
}