顺便把样例的图带上了。

png

// #define ___coding

#ifdef ___coding
#define ___coding1 true
#else
#define ___coding1 false
#endif
#include<cmath>
#include<cassert>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<cstdint>
#include<cstring>
#include<ctime>
#include<limits>
#include<algorithm>
#include<bitset>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<memory>
#include<queue>
#include<stack>
#include<set>
#include<sstream>
#include<string>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
#define up(i,a,b) for(i=a;i<(b);++i)
#define dn(i,a,b) for(i=a;i>(b);--i)
#define pr make_pair
typedef signed char snc;
typedef unsigned char unc;
typedef unsigned short uns;
typedef unsigned uni;
typedef unsigned long unl;
typedef long long ll;
typedef unsigned long long ull;
const int BUF_SIZE(1<<14);
bool ___f;
char ___c,___a[45],*___p,___ibuf[BUF_SIZE+1],*___ib(___ibuf),*___ie(___ibuf),___obuf[BUF_SIZE+1],*___ob(___obuf),*___oe(___obuf+BUF_SIZE);
char& gtch(){if(___ib==___ie)___ie=(___ib=___ibuf)+fread(___ibuf,1,BUF_SIZE,stdin);if(___ib==___ie){return *___ibuf=-1;}return *___ib++;}
void ___flush(){fwrite(___obuf,1,___ob-___obuf,stdout);___ob=___obuf;}
void ptch(char c){if(___ob==___oe)___flush();*___ob=c;++___ob;}
typedef __int128 pll;
typedef unsigned __int128 upll;
void rd(pll &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(upll &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void wt(pll r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(upll r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void rd(bool &r){r=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r|=bool(___c^'0');}}
void rd(char &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}
void rd(short &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(short)(___c^'0');}if(___f){r=~(r-1);}}
void rd(int &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(long &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(ll &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(unc &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}
void rd(uns &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(uns)(___c^'0');}}
void rd(uni &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(unl &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(ull &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(char *s){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=' '&&*s!='\r'&&*s!='\n';++s,*s=gtch());*s=0;}
void rd(char *s,char n){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=n;++s,*s=gtch());*s=0;}
void wt(bool a){ptch('0'+a);}
void wt(char c){ptch(c);}
void wt(short r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(int r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(long r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(ll r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(unc c){ptch(c);}
void wt(uns r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(uni r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(unl r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(ull r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(char *s){for(;*s;++s){ptch(*s);}}
void wt(const char *s){for(;*s;++s){ptch(*s);}}
template<typename T,typename ...T1>void rd(T &a,T1 &...b){rd(a);rd(b...);}
template<typename T,typename ...T1>void wt(T a,T1 ...b){wt(a);wt(b...);}
template<typename T>void RD(T* a,int n=1){while(n--){rd(*a);++a;}}
ll llabs1(ll a){return a<0?-a:a;}
template<typename T>T ___min(T &a,T &b){return a<b?a:b;}
template<typename T,typename ...T1>T ___min(T &a,T &b,T1 &...c){return ___min(a,b=___min(b,c...));}
template<typename T,typename...T1>T min(T a,T1 ...b){return ___min(a,b...);}
template<typename T>T ___max(T &a,T &b){return a>b?a:b;}
template<typename T,typename ...T1>T ___max(T &a,T &b,T1 &...c){return ___max(a,b=___max(b,c...));}
template<typename T,typename...T1>T max(T a,T1 ...b){return ___max(a,b...);}
/*

*/
const int N(6e5+5),L(3);
int n,m,cnt,s[N];
// std::ofstream out;
struct persistent_trie_node{
	int sz;
	persistent_trie_node *son[2];
};
struct persistent_trie{
	typedef persistent_trie_node node;
	node t[N*L],*tot,*root[N];
	void init_node(node* u){
		u->sz=0;u->son[0]=u->son[1]=t;
	}
	node* cpy(node* u){
		++tot;*tot=*u;return tot;
	}
	void insert(node* &u,int k,int l=L-1){
		// if(l==L-1){
		// 	std::cout<<"insert "<<std::bitset<32>(k)<<'\n';
		// }
		bool c((k>>l)&1);
		u=cpy(u);
		++u->sz;
		if(l==-1)return;
		insert(u->son[c],k,l-1);
	}
	int query(int l,int r,int x){
		// std::cout<<"query "<<std::bitset<32>(x)<<'\n';
		bool c;
		int i,res(0);
		node *u(root[l]),*v(root[r]);
		DN(i,L-1,0){
			c=((x>>i)&1)^1;
			// printf("u=%llu v=%llu i=%d c=%d sz=%d,%d\n",u-t,v-t,i,c,u->son[c]->sz,v->son[c]->sz);
			// if(i==0){
			// 	if(u->sz<v->sz){
			// 		res|=1;
			// 	}
			// 	break;
			// }
			if(v->son[c]!=t&&u->son[c]->sz<v->son[c]->sz){
				// printf("goto son[%d]\n",c);
				res|=1<<i;
				u=u->son[c];v=v->son[c];
			}else if(v->son[c^1]!=t){
				// printf("goto son[%d]\n",c^1);
				u=u->son[c^1];v=v->son[c^1];
			}else break;
		}
		return res;
	}
	void clear(){
		init_node(t);
		root[0]=tot=t;
	}
}tree;

void ___main(){
	char o;
	int i,l,r,k;
	// out.open("out.txt");
	tree.clear();
	rd(n,m);
	UP(i,1,n){
		rd(k);
		++cnt;
		s[cnt]=s[cnt-1]^k;
		tree.root[cnt]=tree.root[cnt-1];
		tree.insert(tree.root[cnt],s[cnt]);
	}
	up(i,0,m){
		rd(o,l);
		if(o=='A'){
			++cnt;
			s[cnt]=s[cnt-1]^l;
			tree.root[cnt]=tree.root[cnt-1];
			tree.insert(tree.root[cnt],s[cnt]);
		}else{
			rd(r,k);
			--l;--r;
			if(l==0){
				wt(max(s[cnt]^k,tree.query(l,r,s[cnt]^k)));
			}else{
				wt(tree.query(l-1,r,s[cnt]^k));
			}
			wt('\n');
			// wt(tree.query(l,r,k^s[n]^s[l-1]),'\n');
		}
	}
	// UP(i,0,tree.tot-tree.t){
	// 	printf("%d: %llu %llu %d\n",i,tree.t[i].son[0]-tree.t,tree.t[i].son[1]-tree.t,tree.t[i].sz);
	// 	if(tree.t[i].son[0]!=tree.t){
	// 		out<<i<<' '<<tree.t[i].son[0]-tree.t<<" 0\n";
	// 	}
	// 	if(tree.t[i].son[1]!=tree.t){
	// 		out<<i<<' '<<tree.t[i].son[1]-tree.t<<" 1\n";
	// 	}
	// }
	// out.close();
}
int main(){if(___coding1)freopen("in.txt","r",stdin);___main();___flush();return 0;}