记录编号	583109	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3261]最大区间异或和	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.865 s
提交时间	2023-10-04 16:54:08	内存使用	202.95 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 5e5+10;
int n,m;
int s[N];
class made{
public:
    int f;
    int son[3];
}a[N<<5];
int tot,root[N];
void insert(int x){
    root[x] = ++tot;
    a[tot] = a[root[x-1]];
    a[tot].f = x;
    int now = tot,old = root[x-1];
    for(int i = 31;i >= 0;i--){
        int u = (s[x] >> i) & 1;
        a[now].son[u] = ++tot;
        a[tot] = a[a[old].son[u]];
        a[tot].f = x;
        now = a[now].son[u];
        old = a[old].son[u];
    }
}
int ask(int l,int r,int val){
    if(r == 0)return val;
    int ans = 0,p = root[r];
    for(int i = 31;i >= 0;i--){
        int u = (val >> i) & 1;
        int so = a[p].son[u^1];
        if(so && a[so].f >= l)ans += (1ll << i),p = a[p].son[u^1];
        else p = a[p].son[u];
    } 
    return ans;
}
int main(){
    freopen("xorsum.in","r",stdin);
    freopen("xorsum.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%d",&s[i]);
        s[i] ^= s[i-1];
        insert(i);
    }
    for(int i = 1;i <= m;i++){
        char ch[2];scanf("%s",ch);
        int x,y,z;
        if(ch[0] == 'A'){
            scanf("%d",&s[++n]);
            s[n] ^= s[n-1];
            insert(n);
        }
        else{
            scanf("%d%d%d",&x,&y,&z);
            printf("%d\n",ask(x-1,y-1,z^s[n]));
        }
    }
    
    return 0;
    
}