观察我们目前要求的是$$ans = \max_{l \le k \le r} {(a[k] \oplus a[k+1] \oplus a[k+2] \oplus … \oplus a[N] \oplus x)}$$
令$$s[i] = a[1]\oplus a[2]\oplus …\oplus a[i] $$
容易看出当$j > i$, $$s[i] \oplus s[j] = a[1]\oplus a[2]\oplus …\oplus a[i] \oplus a[1]\oplus a[2]\oplus …\oplus a[i]\oplus a[i+1]\oplus … \oplus a[j]$$
根据异或满足交换律和结合律, 所以我们可以把相同的项移到一起消掉, 得到$$s[i] \oplus s[j] = a[i+1]\oplus a[i+2]\oplus …\oplus a[j]$$
所以我们可以替换为求$$ans = \max_{l \le k \le r} {(\boxed{a[k] \oplus a[k+1] \oplus a[k+2] \oplus … \oplus a[N]} \oplus x)} = \max_{l \le k \le r} (\boxed{s[k-1] \oplus s[N]} \oplus x)$$
即
$$ans = \max_{l \le k \le r} {(\boxed{a[k] \oplus a[k+1] \oplus a[k+2] \oplus … \oplus a[N]} \oplus x)} = \max_{l-1 \le k \le r - 1} (\boxed{s[k] \oplus s[N]} \oplus x)$$
所以我们只需要保存每个点的异或前缀和即可.
再然后在考虑用某种数据结构来保存的时候, 只需要这种数据结构能保证我们检索的时候, 可以限制在l-1 <= k <= r-1 这个区间检索的即可
这就是我们要用到的 可持久化trie树
可持久化trie的结构图可以对照insert函数参考下面童鞋的图:
建议分半个屏幕同时打开并对照代码逐行细看
https://www.acwing.com/solution/content/46534/
https://www.acwing.com/solution/content/26200/
https://www.acwing.com/solution/content/39563/
代码之后还有
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
// 30w初始数据和30w新增, 而10的7次方小于2的24次方, 再加上根节点, 就是说每个数最多需要25位;
const int N = 600010, M = N * 25;
int n, m;
int s[N]; // 前缀和序列
int tr[M][2];
int max_id[M]; // 用于记录当前根节点版本的最大id范围, 更直白的说就是当前点对应要存的数的在前缀和数组s的位置
int root[N], idx;
// i是第i个插入的数的i, p是上一个插入的数的节点号, q是当前节点号, k是现在取到第k位
void insert(int i, int k, int p, int q)
{
// 如果记录结束了
if (k < 0)
{
max_id[q] = i; // 记录当前节点(可能会被后面公用)所能到达的最大范围i
return;
}
// 取出前缀和的二进制表示从右往左数第k位v
// 需要注意的是, 这个s[i]就是我们要存的东西!!!!!
int v = s[i] >> k & 1;
// 如果前一个节点存在当前节点没有的分支, 那就把当前节点的这个空的路径指过去, 这就相当于复制!
if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++idx; // 现在才是正常trie树插入
// 递归插入下一位二进制, tr[q][v]就是我们本轮插入的新节点
// 而前面我们只复制了前一轮的不同v方向的路径, v方向的还没动过, 于是放到p里面等下一轮
// 至于为什么可以放到下一轮, 因为当前q新插入的数字(二进制当前位)是v, 而p的这条路径也是v
// 所以暂时不需要复制
insert(i, k - 1, tr[p][v], tr[q][v]);
// 下面是递归到所有点都插入完成才开始进行的, 所以能把最大max_id递归传递回去
// 每个点的最大范围用子节点最大的值, 然后还能递归传递回去, 因为当前递归层
// 的q, 就是上一层的tr[q][v], 观察易知每个节点都会有对应max_id
max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}
int query(int l, int r, int C)
{
// 选用合适的root, 就是第r-1个节点作为root(-1已在传参前完成)
// 然后根据异或的前缀和性质才能保证在r左边
int p = root[r];
for (int i = 23; i >= 0; i--)
{
// C是s[n] ^ x, 从高位到低位逐位检索二进制每一位上能跟C异或结果最大的数
int v = C >> i & 1;
// 自带判空功能如果没有点, max_id会为-1, 那就肯定不能满足>=l (根据初始化max_id[0] = -1)
// 如果没有这个初始化, max_id[0] 默认为0, 而当l=0 的时候就会令到p误跳到空节点
// 而max_id又同时可以限制当前的点是在l r区间内
// 另外, 如果tr[p][v^1]为空, 那么tr[p][v]就肯定不为空,并在l r区间, 因为根据
// 插入的代码, 每个节点至少有一条当前s[i]的完整路径
// 而如果tr[p][v^1]不为空但maxid小于l, 同理也能选取到tr[p][v]
// printf("max_id[%d]: %d, p: %d, l: %d\n", tr[p][v ^ 1], max_id[tr[p][v ^ 1]], p, l);
if (max_id[tr[p][v ^ 1]] >= l) p = tr[p][v ^ 1];
else p = tr[p][v];
}
return C ^ s[max_id[p]];
}
int main()
{
scanf("%d%d", &n, &m);
// 前缀和, 初始化root[0]
max_id[0] = -1;
root[0] = ++idx;
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] = ++idx;
insert(i, 23, root[i - 1], root[i]);
}
char op[2];
int l, r, x;
while (m--)
{
scanf("%s", op);
if (op[0] == 'A')
{
scanf("%d", &x);
n++;
s[n] = s[n - 1] ^ x;
root[n] = ++idx;
insert(n, 23, root[n - 1], root[n]);
}
else
{
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", query(l - 1, r - 1, s[n] ^ x));
}
}
return 0;
}
根据上面有个小练习: 把insert改成迭代版. 这里可以更清晰看到, max_id其实就是当前”trie新加的部分”对应在s数组的位置
void insert(int i)
{
int p = root[i];
int last_p = 0;
if (i) last_p = root[i-1];
for (int j = 23; j >= 0; j--)
{
int v = s[i] >> j & 1;
tr[p][v] = ++idx;
if(last_p)
{
tr[p][v^1] = tr[last_p][v^1];
last_p = tr[last_p][v];
}
max_id[idx] = i;
p = tr[p][v];
}
max_id[p] = i;
}
搞不懂初始化的insert(0, 23, 0, root[0]);是为了什么.....
搞不懂初始化的insert(0, 23, 0, root[0]);是为了什么.....
这是哪一步在取这个最大值啊,我感觉这好像就是把他存下来而已,看不出哪里在取Max异或和
关于如何获得最大值问题:
首先,举个栗子,假设a = 1100110;x^a要求到最大值,那么x的二进制最高位最优条件是1(和a的最高位取反),然后在最高位1的trie子树下递归,如果x的最高位只有是0,那么就在最高位0的trie子树下递归;依次按照这个条件层层递归;
其次,因为这道题中设定了x的范围是L~R,设R是不变的,就是root[R]中的异或前缀和S[i];L是变化的,那么就需要判断满足x二进制最优条件的trie树是否存在一个数它的下标>=L。这个判断条件等价于最优trie子树下标的最大值是否>=L,我们在代码中用max_id[i]来保存这个最大值。
最后,代码把两个条件结合起来,if (max_id[tr[p][v ^ 1]] >= l) p = tr[p][v ^ 1];确保了两数异或取到最大值。
emmm听听课啊,别想着速通,有一点没理解你就白学了,不如稳扎稳打
max_id[0] = -1不这样赋值的话什么情况下会出现问题?
好问题! 发现了之前理解的一个错误, 现在已更正. 请看query部分注释~
看到大佬代码,在query中加个判断就不需要max_id[0] = -1了
if (max_id[tr[p][u ^ 1]] >= L && tr[p][u ^ 1])
L难道还能等于0吗?
大佬为啥初始化rt0啊
orz
爱了爱了
猫佬 已关注 莫辜负
大佬注释写的很清晰
请问一下那是复制节点的时候v^1是什么意思
v是当前二进制数位上面的数字, 取v^1就是取反, 是去找当前trie前缀相同, 另一个分支上面, 如果存在数字, 就能复制过来. 打字比较抽象, 可以多看看图然后自己画画模拟一下~
前两天已经理解了,谢谢
大爱喵佬
嘿嘿嘿~
大爱喵佬
( ̄▽ ̄)~*
$root$ 和 $max$_$id$ 数组是保存的什么
保存$n$个数字的可持久化trie, 会存在$n$个根节点, 从第$k$个根节点开始访问这个trie的时候, 可以访问到从1~k这些数字的所有内容.
而$root[k]$是第$k$个数字在trie里面根节点的编号,
$max_id[idx]$是当前$idx$节点对应所对应最大的$k$ ($k$指第$k$个数字)
$max_id$用于求前缀和的时候判断某个节点是否超出左边界
Insert函数里的23、0是什么?
23是数据范围够用的二进制位数, 0指哪个0