$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 初始化前缀和s[i] = a[1] ^ a[2] ^ …… ^ a[i]
2. a[p] ^ a[p+1] ^ …… ^ a[n] ^ x = s[p-1] ^ s[n] ^ x
3. 设 C = s[n] ^ x，故只需要求在 l <= p <= r，s[p-1] ^ C 最大即可
4. 用二进制来表示s[i]，max_id[i] 表示这个数在前缀和 s[i] 是第几个数
5. 怎么使 s[p-1] ^ C 最大，可以使高位尽量取与 C 相异的数字

可参考： 最大异或对

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 600010, M = N * 25;

int n,m;
int s[N];
int tr[M][2];
int max_id[M];
int root[N],idx;

void insert(int i,int k,int p,int q)
{
    if(k<0) 
    {
        max_id[q]=i;
        return;
    }

    //表示当前数字的编号是i
    max_id[q]=i;

    //取出当前数从右往左第k位数字
    int v=s[i]>>k&1;
    if(p) tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;

    //递归当前数字的下一位
    insert(i,k-1,tr[p][v],tr[q][v]);
}

int query(int l,int r,int C)
{
    int p=root[r];
    for(int i=23;i>=0;i--)
    {
        int v=C>>i&1;
        if(max_id[tr[p][v^1]]>=l) p=tr[p][v^1];
        else p=tr[p][v];
    }

    return s[max_id[p]]^C;
}

int main()
{
    cin>>n>>m;

    max_id[0]=-1;
    root[0]=++idx;
    insert(0,23,0,root[0]);

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s[i]=s[i-1]^x;
        root[i]=++idx;
        insert(i,23,root[i-1],root[i]);
    }

    char op;
    int l,r,x;
    while(m--)
    {
        cin>>op;

        //添加操作
        if(op=='A')
        {
            cin>>x;
            n++;
            s[n]=s[n-1]^x;
            root[n]=++idx;
            insert(n,23,root[n-1],root[n]);
        }
        //询问操作
        else 
        {
            cin>>l>>r>>x;
            cout<<query(l-1,r-1,s[n]^x)<<endl;
        }
    }

    return 0;
}