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