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;   
}