题意：给定一个非负整数序列{a}，初始长度为N。
有M个操作，有以下两种操作类型： 1、Ax：添加操作，表示在序列末尾添加一个数x，序列的长度N+1。 2、Qlrx：询问操作，你需要找到一个位置p，满足l<=p<=r，使得： a[p] xor a[p+1] xor ... xor a[N] xor x 最大，输出最大是多少。 题解：可持久化trie 用前缀异或来建树，查询就变成了last^x和l到r中a【p】异或最大值是多少 先插入一个0，然后像可持久化线段树那样建树即可，还是挺简单的/************************************************************** Problem: 3261 User: walfy Language: C++ Result: Accepted Time:4584 ms Memory:179416 kb****************************************************************/ //#pragma GCC optimize(2)//#pragma GCC optimize(3)//#pragma GCC optimize(4)//#pragma GCC optimize("unroll-loops")//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include #define fi first#define se second#define db double#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector #define mod 998244353#define ld long double#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pll pair #define pil pair #define pli pair #define pii pair //#define cd complex #define ull unsigned long long#define base 1000000000000000000#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define fin freopen("a.txt","r",stdin)#define fout freopen("a.txt","w",stdout)#define fio ios::sync_with_stdio(false);cin.tie(0)template inline T const& MAX(T const &a,T const &b){return a>b?a:b;}template inline T const& MIN(T const &a,T const &b){return a =mod)a-=mod;}inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;} using namespace std; const double eps=1e-8;const ll INF=0x3f3f3f3f3f3f3f3f;const int N=600000+10,maxn=100000+10,inf=0x3f3f3f3f; struct trie{ int sz,cnt,root[N],ch[N*25][2],num[N*25]; void init() { sz=cnt=0; root[++sz]=++cnt; int now=root[sz]; for(int i=24;i>=0;i--) { ch[now][0]=++cnt; now=ch[now][0]; num[now]++; } } void add(int x) { root[++sz]=++cnt; int now=root[sz],last=root[sz-1]; for(int i=24;i>=0;i--) { ch[now][(x>>i)&1]=++cnt; ch[now][!((x>>i)&1)]=ch[last][!((x>>i)&1)]; now=ch[now][(x>>i)&1]; num[now]=num[ch[last][(x>>i)&1]]+1; last=ch[last][(x>>i)&1]; } } void query(int l,int r,int x) { int now=root[r],last=root[l],ans=0; for(int i=24;i>=0;i--) {// if(now==128)printf("%d %d %d %d\n",now,last,num[ch[now][!((x>>i)&1)]],num[ch[last][!((x>>i)&1)]]); if(num[ch[now][!((x>>i)&1)]]>num[ch[last][!((x>>i)&1)]]) { now=ch[now][!((x>>i)&1)]; last=ch[last][!((x>>i)&1)]; ans+=(1< >i)&1];//,printf("%d %d\n",now,1); last=ch[last][(x>>i)&1]; }// printf("%d--\n",now); } printf("%d\n",ans); } void debug(int now) { printf("%d %d %d %d\n",now,num[now],ch[now][0],ch[now][1]); if(ch[now][0])debug(ch[now][0]); if(ch[now][1])debug(ch[now][1]); }}tree;int main(){ int n,m,sum=0; scanf("%d%d",&n,&m); tree.init(); for(int i=1;i<=n;i++) { int a;scanf("%d",&a); a^=sum;sum=a;tree.add(a);// printf("%d---\n",a); } while(m--) { char op[5];scanf("%s",&op); if(op[0]=='A') { int x;scanf("%d",&x); x^=sum;sum=x;tree.add(x);// printf("%d---\n",x); } else { int l,r,x; scanf("%d%d%d",&l,&r,&x); x^=sum;tree.query(l-1,r,x);// printf("%d+++\n",x); } }// tree.debug(tree.root[2]); return 0;}/*****************5 52 6 4 3 6A 1Q 3 5 4A 4Q 5 7 0Q 3 6 6*****************/