传送门

翻了翻题解，只有我这么蒻不会把后缀异或和转成前缀异或和吗$QAQ$

没有想到转前缀所以蒟蒻暴力维护了后缀异或和。

首先操作离线下来，处理出添加完所有数后数列的状态，直接把所有后缀异或和插入进可持久化$trie$树里。然后倒着处理操作，这样添加就变成了删除。

删除结尾的一个数，剩下的所有后缀异或和都会异或上删掉的数。在全局维护一个$tag$，删一个数就把$tag$异或上它。在查询时只要$tag$这一位上为$1$就要反着走。

不过这题卡常，恰好我这个做法常数比较大，吸氧才能过$QAQ$。

非常神奇的一点：读入字符串用scanf$T$得飞起，换成cin就$A$了。数据有锅？

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 300005

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int siz[maxn<<6],trie[maxn<<6][2],a[maxn<<1],sum[maxn<<1],root[maxn<<1],ans[maxn],top,tag,cnt=1;
#define ls(x) trie[x][0]
#define rs(x) trie[x][1]
struct ORDER{
    int s,l,r,x;    
}o[maxn];
inline void update(int node){
    siz[node]=siz[ls(node)]+siz[rs(node)];
}
void insert(int &node,int ol,int d,int now=25){
    node=++cnt;
    if(now==-1){
        siz[node]=siz[ol]+1;
        return;
    }
    bool k=d&(1<<now);
    trie[node][k^1]=trie[ol][k^1];
    insert(trie[node][k],trie[ol][k],d,now-1);
    update(node);
}
int ask(int node,int ol,int d,int now=25){
    if(now==-1)return 0;
    bool k=(d&(1<<now))^(tag&(1<<now));
    //异或上tag的这一位就相当于：tag这一位上为1方向改变
    if(siz[trie[node][k^1]]-siz[trie[ol][k^1]]>0)return ask(trie[node][k^1],trie[ol][k^1],d,now-1)+(1<<now);
    else return ask(trie[node][k],trie[ol][k],d,now-1);    
}
int main(){
    int n=read(),m=read();
    char ss[2];
    for(register int i=1;i<=n;++i)
        a[i]=read();
    for(register int i=1;i<=m;++i){
        cin>>ss;
        o[i].s=(ss[0]=='Q')+1,o[i].l=read();
        if(o[i].s==1)a[++n]=o[i].l;
        else o[i].r=read(),o[i].x=read();
    }
    for(register int i=n;i;--i)
        sum[i]=sum[i+1]^a[i];
    for(register int i=1;i<=n;++i)
        insert(root[i],root[i-1],sum[i]);
    for(register int i=m;i;--i){
        if(o[i].s==1)tag^=o[i].l;//标记处理
        else ans[++top]=ask(root[o[i].r],root[o[i].l-1],o[i].x);
    }
    while(top)printf("%d\n",ans[top--]);
}