ACM模版

描述


题解

第一次知道原来可持久化并不只是主席树的专利…… Tire 也可以持久化操作……学习了。原谅我对可持久化理解的不够深刻，目前还只是套套模版的样子……至于为什么要用 Tire 倒是十分容易理解，这种求 Xor 最大的题，需要从高位贪心处理，尽量找高位不同的数，找不到向低位继续查找，我们将它桉位拆开看，就是一个 Tire 树了。

很好的一个题，可惜我对可持久化依然是一知半解，先这样，待我找找关于可持久化相关的资料，如果大神们有相关的资料，比较好的可以在评论区推荐给我，在此先谢谢大佬们~~~

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 5e4 + 5;
const int MAGIC = 30;
const int MAXM = MAXN * (MAGIC + 5);

int n, q, tot = 0;
int sum[MAXM];
int root[MAXN];
int son[MAXM][2];
bool bz[MAGIC + 5];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

void insert(int v, int &x, int y)
{
    x = ++tot;
    memcpy(son[x], son[y], sizeof(son[x]));
    sum[x] = sum[y] + 1;
    if (!v)
    {
        return ;
    }
    insert(v - 1, son[x][bz[v - 1]], son[y][bz[v - 1]]);
}

int find(int v, int x, int y)
{
    if (!v)
    {
        return 0;
    }
    if (sum[son[x][bz[v - 1]]] > sum[son[y][bz[v - 1]]])
    {
        return find(v - 1, son[x][bz[v - 1]], son[y][bz[v - 1]]) + (1 << (v - 1));
    }
    return find(v - 1, son[x][1 - bz[v - 1]], son[y][1 - bz[v - 1]]);
}

int main()
{
    scan_d(n), scan_d(q);

    int x;
    for (int i = 1; i <= n; i++)
    {
        scan_d(x);
        for (int j = 0; j < MAGIC; x >>= 1)
        {
            bz[j++] = x & 1;
        }
        insert(MAGIC, root[i], root[i - 1]);
    }

    int l, r;
    while (q--)
    {
        scan_d(x), scan_d(l), scan_d(r);
        for (int j = 0; j < MAGIC; x >>= 1)
        {
            bz[j++] = 1 - (x & 1);
        }
        printf("%d\n", find(MAGIC, root[r + 1], root[l]));
    }

    return 0;
}