可持久化Trie

需要知道一个异或的特点，和前缀和差不多

a[p] xor a[p+1] xor....xor a[n] xor x = a[p-1] xor a[n] xor x

所以我们把a[1...n]的异或和预处理出来，用s[i]表示，用一个可持久化Trie维护

问题就转化成s[n] xor x = val,求一个序列与val异或的最大值

第i个Trie的root对应维护s[1..i]，这样我们在查询值的时候为了保证在[...r-1]之类，只要查询r-1及之前的版本

为了保证在[l-1...]内，我们还需要一个数组latest维护末尾节点是最近一次第几个s的末尾，查询的时候跳过小于l-1的版本即可

这题洛谷上卡常。。根据题目给的范围，24位二进制足够了，没必要开32位，节约时间。。还有各种inline，快读，尽量用上

为了保证能够查询[1..r]，我们还需要给空树插入一个0，保证覆盖整个区间（类似主席树）

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int lowbit(int x){ return x & (-x); }

inline int read(){

    int X = 0, w = 0; char ch = 0;

    while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }

    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();

    return w ? -X : X;

}

inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }

inline int lcm(int a, int b){ return a / gcd(a, b) * b; }

template<typename T>

inline T max(T x, T y, T z){ return max(max(x, y), z); }

template<typename T>

inline T min(T x, T y, T z){ return min(min(x, y), z); }

template<typename A, typename B, typename C>

inline A fpow(A x, B p, C lyd){

    A ans = 1;

    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;

    return ans;

}

const int N = 600005;

int n, m, trie[N*24][2], latest[N*24], s[N], root[N], tot;

inline void insert(int k, int i, int p, int q){

    if(i < 0){

        latest[p] = k;

        return;

    }

    int t = (s[k] >> i) & 1;

    if(q) trie[p][t^1] = trie[q][t^1];

    trie[p][t] = ++tot;

    insert(k, i - 1, trie[p][t], trie[q][t]);

    latest[p] = max(latest[trie[p][0]], latest[trie[p][1]]);

}

inline int query(int cur, int i, int val, int lmt){

    if(i < 0) return s[latest[cur]] ^ val;

    int t = (val >> i) & 1;

    if(latest[trie[cur][t^1]] >= lmt) return query(trie[cur][t^1], i - 1, val, lmt);

    return query(trie[cur][t], i - 1, val, lmt);

}

int main(){

    memset(latest, -1, sizeof latest);

    n = read(), m = read();

    root[0] = ++tot;

    insert(0, 23, root[0], 0);

    for(int i = 1; i <= n; i ++){

        s[i] = s[i - 1] ^ read();

        root[i] = ++tot;

        insert(i, 23, root[i], root[i - 1]);

    }

    while(m --){

        char opt[2]; scanf("%s", opt);

        if(opt[0] == 'A'){

            int x = read();

            root[++n] = ++tot, s[n] = s[n - 1] ^ x;

            insert(n, 23, root[n], root[n - 1]);

        }

        else if(opt[0] == 'Q'){

            int l = read(), r = read(), x = read();

            printf("%d\n", query(root[r - 1], 23, s[n] ^ x, l - 1));

        }

    }

    return 0;

}