原题链接：https://www.luogu.com.cn/problem/P4735
题意解读：已知长度为n的数组a[]，要在l~r范围找到一个p，使得a[p]^a[p+1]^...^a[n]^x最大，求这个最大的异或值。
解题思路：
1、利用前缀和将问题转化
设s[]是a[]的前缀异或数组，要计算a中一段范围l~r的异或，可以借助于s
由于s[r] = a[0]^a[1]^...a[l-1]^a[l]^...^a[r]，s[l-1] = a[0]^a[1]^...^a[l-1]
因此s[r] ^ s[l-1] = a[l]^a[l+1]^...^a[r]
对于a[p]^a[p+1]^...^a[n]^x，可以转化为s[n]^x^s[p-1]，即问题转化为在s[l-1]~s[r-1]范围内找到一个s[p-1]使得s[n]^x与其异或值最大。
要计算与一个数异或最大的值，可以借助于Trie树，但是这里限制条件是要在一个范围内找到与某个数异或的最大值，需要引入一种新的数据结构-持久化Trie树。
2、持久化Trie树介绍
所谓持久化Trie，一般用于01Trie，是指对每一个数字进行加入trie操作时，都建立一个新的根节点，从该根节点可以查找到之前添加的所有的数，具体如何实现呢？我们以2 6 4 3 为例进行Trie添加操作：
添加的过程有以下特点：
- 每添加一个数s[i]，都建立一个根节点root[i]，从root[i]可以查找到s[1]~s[i]所有数
- 当添加s[i]时，对于s[i]的每一个二进制位都新建立节点，对于不在s[i]中的二进制位，复制前一个根的节点
- 如添加6时，trie[6][0]=trie[1][0]是复制前一个根节点，而trie[6][1]=7是新建节点
查找的过程：
要在L~R范围内查找与x异或最大的结果，可以在根为root[R]中去找1~R范围的数，同时用一个maxid[]来记录Trie树中每一个节点所经过的数的最大id，这样在查找最大异或值时，只需要判断相反位节点存在且maxid[]>=L即说明是L~R范围的数，不存在则走相同位的节点。
Trie树操作核心代码：
//将s[id]添加到持久化Trie
void add(int id)
{root[id] = ++idx; //创建当前根节点int cur = root[id]; //当前根int pre = root[id - 1]; //前一个根for(int i = 23; i >= 0; i--){int v = s[id] >> i & 1;trie[cur][!v] = trie[pre][!v]; //相反位复制上一个根trie[cur][v] = ++idx; //对s[i]每个二进制位新建节点maxid[cur] = id; //更新maxidcur = trie[cur][v], pre = trie[pre][v]; //根沿着s[i]的二进制位往下走}maxid[cur] = id; //更新maxid
}//在l~r范围内查找与val异或的最大值
int find(int l, int r, int val)
{int res = 0;int u = root[r]; //根for(int i = 23; i >= 0; i--){int v = val >> i & 1;if(maxid[trie[u][!v]] >= l) //如果相反位的节点存在且最大编号>=l{u = trie[u][!v];res = res * 2 + 1; //异或后1对结果的贡献}else{u = trie[u][v];res = res * 2; //异或后0对结果的贡献}}return res;
}3、最终问题求解
第一步：计算前缀异或
第二步：建立持久化Trie
第三步：范围查找最大异或值
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 600005, M = N * 24;
int s[N]; //前缀异或数组
int root[N]; //所有版本trie的根节点
int trie[M][2], idx, maxid[M]; //trie树，maxid[]保存经过某个节点的数的最大s编号
int n, m;
char op;
int l, r, x;//将s[id]添加到持久化Trie
void add(int id)
{root[id] = ++idx; //创建当前根节点int cur = root[id]; //当前根int pre = root[id - 1]; //前一个根for(int i = 23; i >= 0; i--){int v = s[id] >> i & 1;trie[cur][!v] = trie[pre][!v]; //相反位复制上一个根trie[cur][v] = ++idx; //对s[i]每个二进制位新建节点maxid[cur] = id; //更新maxidcur = trie[cur][v], pre = trie[pre][v]; //根沿着s[i]的二进制位往下走}maxid[cur] = id; //更新maxid
}//在l~r范围内查找与val异或的最大值
int find(int l, int r, int val)
{int res = 0;int u = root[r]; //根for(int i = 23; i >= 0; i--){int v = val >> i & 1;if(maxid[trie[u][!v]] >= l) //如果相反位的节点存在且最大编号>=l{u = trie[u][!v];res = res * 2 + 1; //异或后1对结果的贡献}else{u = trie[u][v];res = res * 2; //异或后0对结果的贡献}}return res;
}int main()
{cin >> n >> m;maxid[0] = -1; //不存在的节点maxid=-1，便于find中比较add(0); //第一个数添加0，使得便于区间计算for(int i = 1; i <= n; i++){cin >> s[i];s[i] = s[i - 1] ^ s[i]; //计算前缀异或add(i); //添加到持久化Trie} while(m--){cin >> op;if(op == 'A'){cin >> x;s[n + 1] = s[n] ^ x;n++;add(n);}else{cin >> l >> r >> x;cout << find(l - 1, r - 1, x ^ s[n]) << endl;}}
}
