WA 成 10 分。

我的做法是插入的时候把 trie 树上每个前缀异或和所对应原数列下标，将他加入每个祖先节点的 vector 中。

然后由于一个一个加入，下标是单调递增的，所以可以二分。

查询的时候还是贪心，多判断一个贪心的节点子树内是否存在下标在 $[l,r]$ 内的节点。（这里二分，查询大于等于 $l$ 的最小编号是否 小于等于 $r$，满足就贪，不满足就走另一个）

复杂度应该是 两个 log 的，但是没T？WA 了 9 个点，唯一 AC 的是评论区里的 hack 数据

求助大佬，谢谢

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAXM=4000005;
int q;char s;
int ch[MAXM][2],n,pre,tot;
vector<int>v[MAXM];
inline void insert(int pos,int S){
	int x=0;
	v[x].push_back(pos);
	for(register int i=31;i>=0;--i){
		int id=(S>>i&1);
		if(!ch[x][id])ch[x][id]=++tot;
		x=ch[x][id];
		v[x].push_back(pos);
	}
}
inline bool check(int x,int l,int r){
	int t=v[x][lower_bound(v[x].begin(),v[x].end(),l)-v[x].begin()];
	return t<=r;
}
inline int ask(int S,int l,int r){
	int x=0,ret=0;
	for(register int i=31;i>=0;--i){
		int id=(S>>i&1),els=id^1;
		if(ch[x][0]==0&&ch[x][1]==0)break;
		
		if(ch[x][els]&&check(ch[x][els],l,r)){
			x=ch[x][els];
			ret|=(1<<i);
		}else if(ch[x][id]){
			x=ch[x][id];
		}
	}
	return ret;
}
signed main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	n=read();q=read(); 
	insert(0,pre=0);
	for(register int i=1;i<=n;++i){
		pre^=read();
		insert(i,pre);
	}
	while(q--){
		scanf(" %c",&s);
		if(s=='A'){
			pre=pre^read();
			insert(++n,pre);
		}else {
			int l=read(),r=read();
			int x=read()^pre;
			printf("%d\n",ask(x,l-1,r-1));
		}
	}
	return 0;	
}