1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 6e5+10;
int rt[N],cnt[N*28];
int ch[N*28][2];
int qz[N];
int tt = 1;
int n,m;
void insert(int now, int pre, int t, int x){
if(t<0)return ;
int i = (x>>t)&1;
ch[now][!i] = ch[pre][!i];
ch[now][i] = tt++;
cnt[ch[now][i]]= cnt[ch[pre][i]] + 1;
insert(ch[now][i], ch[pre][i], t - 1, x);
}
int query(int now,int pre,int t,int x){
if(t<0)return 0;
int i = (x>>t)&1;
if(cnt[ch[pre][!i]] > cnt[ch[now][!i]]){
return (1<<t)+query(ch[now][!i],ch[pre][!i],t-1,x);
}else{
return query(ch[now][i],ch[pre][i],t-1,x);
}
}
int main(){
scanf("%d%d",&n,&m);
int a,b,c,i,j;
char s[5];
rt[0]=tt++;
insert(rt[0],0,25,0);
for(a=1;a<=n;a++){
scanf("%d",&b);
qz[a]=qz[a-1]^b;
rt[a]=tt++;
insert(rt[a],rt[a-1],25,qz[a]);
}
for(a=1;a<=m;a++){
scanf("%s",s);
if(s[0]=='A'){
scanf("%d",&b);
n++;
qz[n]=qz[n-1]^b;
rt[n]=tt++;
insert(rt[n],rt[n-1],25,qz[n]);
}else{
scanf("%d%d%d",&i,&j,&b);
i--;j--;
if(i==0)printf("%d\n",query(0,rt[j],25,b^qz[n]));
else printf("%d\n",query(rt[i-1],rt[j],25,b^qz[n]));
}
}
}
|