C09 可持久化字典树（Trie）

// 可持久化01Trie O(n*23)
#include<bits/stdc++.h>
using namespace std;
const int N = 600010;
int n, m, idx, cnt;
int rt[N], ch[N * 25][2], siz[N * 25];

void insert(int v)
{
    rt[++idx] = ++cnt;   // 新根开点
    int x = rt[idx - 1]; // 旧版
    int y = rt[idx];     // 新版
    for (int i = 23; i >= 0; i--)
    {
        int j = v >> i & 1;
        ch[y][!j] = ch[x][!j]; // 异位继承
        ch[y][j] = ++cnt;      // 新位开点
        x = ch[x][j];
        y = ch[y][j];        // 走位
        siz[y] = siz[x] + 1; // 新位多1
    }
}
int query(int x, int y, int v)
{
    int ans = 0;
    for (int i = 23; i >= 0; i--)
    {
        int j = v >> i & 1;
        if (siz[ch[y][!j]] > siz[ch[x][!j]])
            x = ch[x][!j], y = ch[y][!j], ans += (1 << i);
        else
            x = ch[x][j], y = ch[y][j];
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    insert(0); // 插个左边界0
    int s=0;
    for (int i = 1,x; i <= n; i++)
    {
        scanf("%d", &x);
        s ^= x;
        insert(s);
    }
    for(int i=1,l,r,x;i<=m;i++)
    {
        char op[5];scanf("%s", op);
        if (op[0] == 'A')
        {
            scanf("%d", &x);
            s ^= x;
            insert(s);
        }
        else
        {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(rt[l - 1], rt[r], s ^ x));
        }
    }
}

可持久化 $Trie$ 真好写...

我们看两个操作，添加操作没什么好说的，查询操作看起来很奇怪，但是如果转为前缀异或和数组$s[i]$，并把 $x$ 异或上 $s[n]$ 的话...

我们发现实际上就是考虑一个区间的数和 $x$ 异或后的最大异或和。

这样我们建一棵可持久化 $Trie$ ,每个节点存它的数字个数，查询的时候从高位到低位贪心走路就好。

另外注意一个坑点，就是如果查询区间左端点是1的话， $x$ 异或上 $0$ 可能是最大的，要把这种情况考虑进去。

最后，如果不知道可持久化Trie的话，其实根据主席树的建树方法脑补一下就好，还是很好写的。

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
#define maxn 600009
int rt[maxn],cnt[maxn*28];
int ch[maxn*28][2];
int qz[maxn];
int tt=1;
int n,m;
void ins(int a,int b,int t,int x) {
    if(t<0) return;
    int i=(x>>t)&1;
    ch[a][!i]=ch[b][!i];
    ch[a][i]=tt++;
    cnt[ch[a][i]]=cnt[ch[b][i]]+1;
    ins(ch[a][i],ch[b][i],t-1,x);
}
int qu(int a,int b,int t,int x) {
    if(t<0) return 0;
    int i=(x>>t)&1;
    if(cnt[ch[b][!i]]>cnt[ch[a][!i]]) {
        return (1<<t)+qu(ch[a][!i],ch[b][!i],t-1,x);
    }
    else {
        return qu(ch[a][i],ch[b][i],t-1,x);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int a,b,c,i,j;
    char s[5];
    rt[0]=tt++;
    ins(rt[0],0,25,0);
    for(a=1;a<=n;a++) {
        scanf("%d",&b);
        qz[a]=qz[a-1]^b;
        rt[a]=tt++;
        ins(rt[a],rt[a-1],25,qz[a]);
    }
    for(a=1;a<=m;a++) {
        scanf("%s",s);
        if(s[0]=='A') {
            scanf("%d",&b);
            n++;
            qz[n]=qz[n-1]^b;
            rt[n]=tt++;
            ins(rt[n],rt[n-1],25,qz[n]);
        }
        else {
            scanf("%d%d%d",&i,&j,&b);
            i--;j--;
            if(i==0) printf("%d\n",qu(0,rt[j],25,b^qz[n]));
            else printf("%d\n",qu(rt[i-1],rt[j],25,b^qz[n]));
        }
    }
    return 0;
}