可持久化Trie学习笔记

shiroi · 2019-12-03 18:32:38 · 个人记录

可持久化Trie和可持久化线段树相似，每次只修改被添加或值被修改的节点，而保留没有被改动的节点。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN = 600005;
int bin[30],a[MAXN],b[MAXN],root[MAXN];
int ch[MAXN*24][2],sum[MAXN*24];
int n,m,cnt;

inline int insert(int x,int val)
{
    int tmp,y; tmp=y=++cnt;
    for(int i=23;i>=0;i--)
    {
        ch[y][0]=ch[x][0]; ch[y][1]=ch[x][1];
        int t=val&bin[i];t>>=i; sum[y]=sum[x]+1;
        x=ch[x][t]; ch[y][t]=++cnt; y=ch[y][t];
    }
    sum[y]=sum[x]+1; return tmp;
}

inline int query(int l,int r,int val)
{
    int tmp=0;
    for(int i=23;i>=0;i--)
    {
        int t=val&bin[i]; t>>=i;
        if(sum[ch[r][t^1]]-sum[ch[l][t^1]])
            tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1];
        else r=ch[r][t],l=ch[l][t];
    }
    return tmp;
}

int main()
{
    bin[0]=1; n=read()+1; m=read();
    for(int i=1;i<30;i++)
        bin[i]=bin[i-1]<<1;
    for(int i=2;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=b[i-1]^a[i];
    for(int i=1;i<=n;i++)
        root[i]=insert(root[i-1],b[i]);
    char ch[5]; int l,r,x;
    while(m--)
    {
        scanf("%s",ch);
        if(ch[0]=='A')
        {
            a[++n]=read(); b[n]=b[n-1]^a[n];
            root[n]=insert(root[n-1],b[n]);
        }
        else 
        {
            l=read(); r=read(); x=read();
            printf("%d\n",query(root[l-1],root[r],b[n]^x));
        }
    }
    return 0;
}