<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

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

1. A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N$ 增大 $1$。
2. Q l r x：询问操作，你需要找到一个位置 $p$，满足 $l \\le p \\le r$，使得：$a\[p\]\\ xor\\ a\[p+1\]\\ xor\\ …\\ xor\\ a\[N\]\\ xor\\ x$ 最大，输出这个最大值。

输入格式

第一行包含两个整数 $N，M$，含义如问题描述所示。

第二行包含 $N$ 个非负整数，表示初始的序列 $A$。

接下来 $M$ 行，每行描述一个操作，格式如题面所述。

输出格式

每个询问操作输出一个整数，表示询问的答案。

每个答案占一行。

数据范围

$N,M \\le 3 \\times 10^5, 0 \\le a\[i\] \\le 10^7$。

输入样例：

5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4 
Q 5 7 0 
Q 3 6 6

输出样例：

4
5
6

思路

可持久化线段树的博客
可持久化$\text{tire}$树类似可持久化线段树，就是变为按$0,1$来区分左子树和右子树。
我们设$s$是$a$的异或前缀和，即$s_i=a_1\oplus a_2\oplus \cdots\oplus a_i$，所以$[l,r]$的异或值为$s_r\oplus s_{l-1}$，本题要求$\underset{k\in [l,r]}\max\{ a_k\oplus a_{k+1}\oplus \cdots \oplus a_n \oplus val\}=\underset{k\in [l,r]}\max\{ s_n\oplus s_{k-1}\oplus val\}$，设$x=s_n\oplus val$，所以我们可以用$\text{trie}$树来求$s_i$与$x$异或的最大值。但是本题会限制求得范围$[l,r]$，所以我们可以用可持久化$\text{trie}$树来保存从$1\sim n$的每次历史记录，然后我们给每一个点加一个时间，这个时间就是最小的插入编号（$1\sim n$），也就是方便判断这个点能不能用。
插入时类似主席树，重点在查询。我们从$s_r$开始循环，每一棵$\text{trie}$树只会走到前面的节点，所以这就把答案限制在$[1,r]$里，由于每一个点都加了一个时间，所以我们不能走时间$< l-1$的点（注意：是小于，没有等于）。

代码

#include <iostream>
using namespace std;
const int N = 600010,M = 23;
int n,m;
int rt[N],tr[N * M][2],id[N * M],idx;
int s[N];
void insert (int p,int q,int x,int k) {
    id[p] = x;
    if (k < 0) return ;
    int c = s[x] >> k & 1;
    if (q) tr[p][c ^ 1] = tr[q][c ^ 1];
    tr[p][c] = ++idx;
    insert (tr[p][c],tr[q][c],x,k - 1);
}
int query (int p,int x,int k,int minx) {
    if (k < 0) return s[id[p]] ^ x;
    int c = x >> k & 1;
    if (id[tr[p][c ^ 1]] >= minx) return query (tr[p][c ^ 1],x,k - 1,minx);
    return query (tr[p][c],x,k - 1,minx);
}
int main () {
    cin >> n >> m;
    id[0] = -1,rt[0] = ++idx;
    insert (rt[0],0,0,M);
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        rt[i] = ++idx,s[i] = s[i - 1] ^ x;
        insert (rt[i],rt[i - 1],i,M);
    }
    while (m--) {
        char op;
        cin >> op;
        if (op == 'A') {
            int x;
            cin >> x;
            rt[++n] = ++idx,s[n] = s[n - 1] ^ x;
            insert (rt[n],rt[n - 1],n,M);
        }
        else {
            int l,r,x;
            cin >> l >> r >> x;
            cout << query (rt[r - 1],s[n] ^ x,M,l - 1) << endl;
        }
    }
    return 0;
}