思路比较显然

我这里就只放一下可持久化01trie的板子

const int N = 6e5 + 10;

const int M = N * 30;

struct TREE{
	int root[N];
	int t[M][2], num[M];
	int cnt = 0;
	int clone(int i){
		int rt = ++cnt;
		t[rt][0] = t[i][0];
		t[rt][1] = t[i][1];
		num[rt] = num[i] + 1;
		return rt;
	}
	int insert(int x,int i){
		int rt = clone(i);
		for(int p = 25,u = rt; p >= 0; p--){
			int w = (x >> p) & 1;
			i = t[i][w];
			int v = clone(i);
			u = t[u][w] = v;
		}
		return rt;
	}
	int qry(int x,int u,int v){
		int ans = 0;
		for(int p = 25;p >= 0; p--){
			int w = (x >> p) & 1;
			if(num[t[v][w^1]] > num[t[u][w^1]]){
				ans += 1 << p;
				u = t[u][w^1];
				v = t[v][w^1];
			}
			else{
				u = t[u][w];
				v = t[v][w];
			}
		}
		return ans;
	}
}T;

另一种写法

const int N = 6e5 + 10;

const int M = N * 30;

struct node{
	int nxt[2], num;
}; 

struct TREE{
	int root[N];
	node t[M];
	int cnt = 0;
	int clone(int i){
		int rt = ++cnt;
		t[rt] = t[i];
		t[rt].num++;
		return rt;
	}
	int insert(int x,int i){
		int rt = clone(i);
		for(int p = 25,u = rt; p >= 0; p--){
			int w = (x >> p) & 1;
			i = t[i].nxt[w];
			int v = clone(i);
			u = t[u].nxt[w] = v;
		}
		return rt;
	}
	int qry(int x,int u,int v){
		int ans = 0;
		for(int p = 25;p >= 0; p--){
			int w = (x >> p) & 1;
			if(t[t[v].nxt[w^1]].num > t[t[u].nxt[w^1]].num){
				ans += 1 << p;
				u = t[u].nxt[w^1];
				v = t[v].nxt[w^1];
			}
			else{
				u = t[u].nxt[w];
				v = t[v].nxt[w];
			}
		}
		return ans;
	}
}T;

code

#include <bits/stdc++.h>
using namespace std;

bool mlest;

double tlest, tleed;

inline int R(){
	int x = 0, f = 1;char ch = getchar();
	while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}

inline void W(int x){
	if(x < 0){x = -x;putchar('-');}
	if(x > 9) W(x/10);putchar(x%10+'0');
}

const int N = 6e5 + 10;

const int M = N * 30;

struct TREE{
	int root[N];
	int t[M][2], num[M];
	int cnt = 0;
	int clone(int i){
		int rt = ++cnt;
		t[rt][0] = t[i][0];
		t[rt][1] = t[i][1];
		num[rt] = num[i] + 1;
		return rt;
	}
	int insert(int x,int i){
		int rt = clone(i);
		for(int p = 25,u = rt; p >= 0; p--){
			int w = (x >> p) & 1;
			i = t[i][w];
			int v = clone(i);
			u = t[u][w] = v;
		}
		return rt;
	}
	int qry(int x,int u,int v){
		int ans = 0;
		for(int p = 25;p >= 0; p--){
			int w = (x >> p) & 1;
			if(num[t[v][w^1]] > num[t[u][w^1]]){
				ans += 1 << p;
				u = t[u][w^1];
				v = t[v][w^1];
			}
			else{
				u = t[u][w];
				v = t[v][w];
			}
		}
		return ans;
	}
}T;

int n, m;

int s;

void read(){
	cin >> n >> m;
	T.root[0] = T.insert(0,0);
	for(int i = 1;i <= n; i++){
		int x; 
		cin >> x; 
		s ^= x; 
		T.root[i] = T.insert(s,T.root[i-1]);
	}
}

void init(){

}

void compute(){
	for(int i = 1;i <= m; i++){
		char op;
		cin >> op;
		if(op == 'A'){
			int x; 
			cin >> x; 
			s ^= x; 
			n++; 
			T.root[n] = T.insert(s,T.root[n-1]);
		}
		else{
			int l, r, x;
			cin >> l >> r >> x;
			l--, r--;
			if(l == 0)
			cout << T.qry(x^s,0,T.root[r]) << '\n';
			else 
			cout << T.qry(x^s,T.root[l-1],T.root[r]) << '\n';
		}
	}
}

void clear(){

}

void run() { read(); init(); compute(); clear(); }

bool mleed;

void wa() { cout << "\n" << tleed-tlest << "ms\n" << (&mleed-&mlest-1)/1024.0/1024.0 << "MB\n"; }

void fre(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int main(){
//	fre("");
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	tlest = clock();
	run();
	tleed = clock();
//	wa();
	return 0;
}