Tire树 可持久化数据结构 T3 256. 最大异或和 - AcWing题库 给定一个非负整数序列 ,初始长度为

个操作,有以下两种操作类型:

  1. A x:添加操作,表示在序列末尾添加一个数 ,序列的长度 增大
  2. 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 树存储, 类似于这样: image.png 最多有 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;
}