Tire树 可持久化数据结构 T3 256. 最大异或和 - AcWing题库 给定一个非负整数序列 ,初始长度为 。
有 个操作,有以下两种操作类型:
A x
:添加操作,表示在序列末尾添加一个数 ,序列的长度 增大 。Q l r x
:询问操作,你需要找到一个位置 ,满足 ,使得: 最大,输出这个最大值。
输入格式
第一行包含两个整数 ,含义如问题描述所示。
第二行包含 个非负整数,表示初始的序列 。
接下来 行,每行描述一个操作,格式如题面所述。
输出格式
每个询问操作输出一个整数,表示询问的答案。
每个答案占一行。
数据范围
。
输入样例:
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
输出样例:
4
5
6
思路
若用数组来处理, 在求第二个操作时会用 的复杂度来更新, 查询为 , 计算异或和为 。 有关区间的可以先考虑前缀和优化, 设 , 则新加入的数的 , 很好解决。第二个操作则可以利用异或运算相同则减去的性质, 可以表示为: 其中 是常数, 我们只需要枚举p, 找到使得这个结果最大的值就行。
于是问题转化为, 在 区间内找到一点 使得 最大。区间查找似乎有很多种算法, 比如二分, 但这里不一定满足两段性, 又或者线段树, 但这里 又是会变化的值, 得经常更新。
那么有没有什么数据结构是可以满足这种异或和查询需求的呢? 既然是异或, 进一步思考可以去二进制方面考虑。 在 最大异或对 题目中, 有一种利用 Tire 树 贪心求得 在序列 中找一个数 , 使得其与给定的 计算出的 值最大。
把题目输入的序列用 Tire 树存储, 类似于这样:
设 最多有 24 位。从根节点开始找, C 的第一位是 1, 故若想要 最大, 的二进制第一位最好是 0, 这样异或之后结果二进制第一位就是 1。 反之, 若 C 的第一位是 0, 则就去找 1。
采用这种方式来搜索, 最多搜索 24 次(题目数据最大也就24个二进制位), 就能搜到结果, 基本优化成 。
但题目这里是有区间限制, 我们先考虑 的情况。因为每次插入都是插入到最后一个, 若采用持久化操作, 则从 会有 个版本, 至于 则只需要访问 的版本即可搜到 的结果, 且不会被之后插入的元素干扰。
再加上 左区间的限制, 当我们在 中搜索时, 可以通过这种方法提前剪枝, 保证在 区间内: 在根节点向下两个子树中, 若在子树里存在一个点的下标 , 即有成立解, 则搜左子树。 该条件等价于 ⇐> 左子树的最大下标 ⇐ L。 故可以增加一个节点信息 , 表示当前子树中能搜到的下标最大值。
持久化数据结构的题目得去计算空间复杂度, 因为这种操作会增加很多空间用来存储之前的版本。
这里共有 3e5 个节点, 以及 3e5 个操作, 故总的版本节点就是 6e5, 每操作一次就会多一个版本节点。而 Tire 树的节点, 每插入一个数最多会增加 24 个节点, 故满打满算是 6e5 * 25。
再看具体数组定义:
tr[M][2]
max_id[M]
root[N]
s[N]
加起来总共是 。而每个 int 占 4 个字节, 因此总共会用 , 题目限制 故可以通过。
如果会爆掉的话, 就看题目的限制, 顶格去设置, 反推出来应该开多少个节点。比如 256MB, 用 240MB 反推出来 N 和 M 的定义, 也不能拉满, 因为程序运行也得用一些。
query的时候, 因为找的是p-1, 而p是在 L,R 区间内, 那么 p-1 就在 L-1, R-1 区间内。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 6e5, M = 24 * N;
int root[M];
int tr[M][2], maxid[M];
int s[N], idx;
int n,m;
void insert(int u, int k, int p, int q)
{
if(k < 0)
{
maxid[q] = u;
return;
}
int v = s[u] >> k & 1;
if(p) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++idx;
insert(u, k - 1, tr[p][v], tr[q][v]);
maxid[q] = max(maxid[tr[q][v]], maxid[tr[q][v ^ 1]]);
}
int query(int r, int C , int l)
{
int p = r;
for(int i = 23; i >= 0; i--)
{
int v = C >> i & 1;
if(maxid[tr[p][v ^ 1]] >= l) p = tr[p][v ^ 1];
else p = tr[p][v];
}
return s[maxid[p]] ^ C;
}
int main()
{
cin >> n >> m;
maxid[0] = -1;
root[0] = ++idx;
insert(0, 23, 0, root[0]);
for(int i = 1; i <= n; i++)
{
cin >> s[i];
root[i] = ++idx;
s[i] ^= s[i - 1];
insert(i, 23, root[i - 1], root[i]);
}
char op[2];
int l, r, x;
while(m--)
{
cin >> op;
if(op[0] == 'A')
{
cin >> x;
++n;
s[n] = s[n - 1] ^ x;
root[n] = ++idx;
insert(n, 23, root[n - 1], root[n]);
}
else {
cin >> l >> r >> x;
cout << query(root[r - 1], x ^ s[n], l-1) << endl;
}
}
return 0;
}