51nod 1295 XOR key | 可持久化Trie树

时间：2021-05-05 17:09:05

51nod 1295 XOR key

这也是很久以前就想做的一道板子题了……学了一点可持久化之后我终于会做这道题了！

给出一个长度为N的正整数数组A，再给出Q个查询，每个查询包括3个数，L, R, X (L <= R)。求A[L] 至 A[R] 这R - L + 1个数中，与X 进行异或运算(Xor)，得到的最大值是多少？

Input

第1行：2个数N, Q中间用空格分隔，分别表示数组的长度及查询的数量(1 <= N <= 50000, 1 <= Q <= 50000)。

第2 - N+1行：每行1个数，对应数组A的元素(0 <= A[i] <= 10^9)。

第N+2 - N+Q+1行：每行3个数X, L, R，中间用空格分隔。（0 <= X <= 10^9，0 <= L <= R < N)

Output

输出共Q行，对应数组A的区间[L,R]中的数与X进行异或运算，所能得到的最大值。

可持久化Trie树，就类似于昨天我写的可持久化线段树。

每次想要修改一个节点的时候，不直接在原来的节点上进行修改，而是在旁边新建一个点，复制原来点的信息，并在新点上面修改。每次通过访问历史根节点来访问历史版本。

配合离线询问，然后从左往右把数组中的数加入Trie树中，对于每个询问[l, r]，可以通过第r棵Trie树与第l - 1棵Trie树相减得到区间中新建出来的Trie树，在上面进行正常的异或最大查询即可。

时间、空间复杂度都是\(O(32*(n + Q))\)。

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <iostream>

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef unsigned long long ll;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

        if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

        x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 50005, M = 3000000;

int n, Q, idx = 1, a[N], root[N] = {1}, son[M][2], sze[M];

void insert(int i, int x){

    int now = root[i] = ++idx;

    int old = root[i - 1];

    for(int i = 31; i >= 0; i--){

        sze[now] = sze[old] + 1;

        if((x >> i) & 1) son[now][0] = son[old][0], son[now][1] = ++idx;

        else son[now][1] = son[old][1], son[now][0] = ++idx;

        now = son[now][(x >> i) & 1];

        old = son[old][(x >> i) & 1];

    }

    sze[now] = sze[old] + 1;

}

int query(int l, int r, int x){

    int old = root[l], now = root[r], ans = 0;

    for(int i = 31; i >= 0; i--){

        bool dir = (x >> i) & 1;

        int delta_sze = sze[son[now][!dir]] - sze[son[old][!dir]];

        if(delta_sze) now = son[now][!dir], old = son[old][!dir], ans = ans << 1 | 1;

        else now = son[now][dir], old = son[old][dir], ans = ans << 1;

    }

    return ans;

}

int main(){

    read(n), read(Q);

    for(int i = 1; i <= n; i++)

        read(a[i]);

    for(int i = 1; i <= n; i++)

        insert(i, a[i]);

    int l, r, x;

    while(Q--){

        read(x), read(l), read(r);

        write(query(l, r + 1, x)), enter;

    }

    return 0;

}

//P.S. 没看见原题中数组从0开始数，白检查半天……

//错误：数组开小了……要不下次用指针吧……？

相关文章