可持久化Trie树模板

Black_Gzombie · 2019-09-17 16:40:07 · 个人记录

Luogu P4735 最大异或和

#include <iostream>
#include <cstdio>
#define rg register
using namespace std;

const int maxn = 600005;
int n,m,tot;
int s[maxn];
int trie[maxn*24][2],latest[maxn*24];
int T[maxn];

inline int read()
{
    rg int x=0;rg char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}

void insert(int i,int k,int p,int q)
{
    if(k<0)
    {
        latest[q]=i;return;
    }
    rg int c=s[i]>>k&1; //取出k+1位 
    if(p)trie[q][c^1]=trie[p][c^1]; //另外一边和前面一样
    trie[q][c]=++tot;
    insert(i,k-1,trie[p][c],trie[q][c]);
    latest[q]=max(latest[trie[q][0]],latest[trie[q][1]]);
}

int query(int now,int val,int k,int L)
{
    if(k<0)return s[latest[now]]^val;
    int c=val>>k&1;
    if(latest[trie[now][c^1]]>=L)
        return query(trie[now][c^1],val,k-1,L);
    else return query(trie[now][c],val,k-1,L);
}

int main()
{
    //freopen("testdata.in","r",stdin);
    //freopen("ans.txt","w",stdout);

    scanf("%d%d",&n,&m);
    latest[0]=-1;T[0]=++tot;
    insert(0,23,0,T[0]);
    for(rg int i=1;i<=n;i++)
    {
        int a;scanf("%d",&a);
        s[i]=s[i-1]^a;
        T[i]=++tot;
        insert(i,23,T[i-1],T[i]);
    }
    for(rg int i=1;i<=m;i++)
    {
        char op;scanf("%s",&op);
        if(op=='A')
        {
            int x;scanf("%d",&x); 
            T[++n]=++tot;
            s[n]=s[n-1]^x;
            insert(n,23,T[n-1],T[n]);
        }
        else
        {
            rg int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            printf("%d\n",query(T[r-1],s[n]^x,23,l-1));
        }
    }
    return 0;
}