P4735 最大异或和

给定一个非负整数序列 \(\{a\}\)，初始长度为\(n\)。

有 \(m\) 个操作，有以下两种操作类型：

1. A x：添加操作，表示在序列末尾添加一个数 \(x\)，序列的长度 \(n+1\)。
2. Q l r x：询问操作，你需要找到一个位置 \(p\)，满足\(l \le p \le r\)，使得： $
   a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x$ 最大，输出最大是多少。

\(N,M \le 300000\)，\(0 \le a[i] \le 10^7\)。

首先对 \(\oplus\) 取前缀和，得到 \(sum\) 数组，然后对于操作2就变成了求 \(sum[p-1]\oplus sum[N]\oplus x\) ， \(p\in [l,r]\) 。其中后两项可以直接求，前面一项可以在Trie树上贪心求。问题就在于区间 \([l,r]\) 了，可以将Trie可持久化就可以了。具体来说将每个节点创建一个 \(maxn\) 值，表示所在子树中最大的前缀值，若 \(l\leq maxn\) 则可以查询，否则不能走该节点。

#include<bits/stdc++.h>
using namespace std;
int n,m;
namespace Trie{
	int trie[80000005][2],tcnt,latest[80000005];
	int s[600005],root[600005];
	void insert(int i,int k,int p,int q){
		if(k<0){
			latest[q]=i;
			return;
		}
		int c=(s[i]>>k)&1;
		if(p)
			trie[q][c^1]=trie[p][c^1];
		trie[q][c]=++tcnt;
		insert(i,k-1,trie[p][c],trie[q][c]);
		latest[q]=max(latest[trie[q][0]],latest[trie[q][1]]);
	}
	
	int query(int now,int val,int k,int L){
		if(k<0)
			return s[latest[now]]^val;
		int c=(val>>k)&1;
		if(latest[trie[now][c^1]]>=L)
			return query(trie[now][c^1],val,k-1,L);
		else return query(trie[now][c],val,k-1,L);
	}
}

using namespace Trie;
int main(){
	scanf("%d %d",&n,&m);
	latest[0]=-1;
	root[0]=++tcnt;
	insert(0,23,0,root[0]);
	for(int i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		s[i]=s[i-1]^x;
		root[i]=++tcnt;
		insert(i,23,root[i-1],root[i]);
	}
	for(int i=1;i<=m;++i){
		char c;
		do{
			c=getchar();
		}while(c!='A' && c!='Q');
		if(c=='A'){
			int x;
			scanf("%d",&x);
			root[++n]=++tcnt;
			s[n]=x^s[n-1];
			insert(n,23,root[n-1],root[n]);
		}
		else{
			int l,r,x;
			scanf("%d %d %d",&l,&r,&x);
			printf("%d\n",query(root[r-1],s[n]^x,23,l-1));
		}
	}
	return 0;
}