BZOJ 3261 最大異或和（可持久化trie）

題目大意

給定一個非負整數序列{a}，初始長度為N。

有M個操作，有以下兩種操作類型：

1、Ax：添加操作，表示在序列末尾添加一個數x，序列的長度N+1。

2、Qlrx：詢問操作，你需要找到一個位置p，滿足l<=p<=r，使得：

a[p] xor a[p+1] xor … xor a[N] xor x 最大，輸出最大是多少。

範圍是3e5

分析

帶區間的二進制trie，但是沒有修改，隻是在末尾加入，是以直接可持久化二進制trie貪心查找即可。

我也不知道為什麼這麼慢，但是我知道了遞歸和非遞歸時間差不多。

代碼

遞歸和非遞歸都在裡面了。

#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=+,N=,maxv=maxn**N;
namespace IStream{  
    const int L=<<;  
    char buffer[L],*S,*T;  
    inline char Get_Char()  
    {  
        if(S==T)  
        {  
            T=(S=buffer)+fread(buffer,,L,stdin);  
            if(S==T) return EOF;  
        }  
        return *S++;  
    }  
    inline void Rd(int &re) 
    {  
        char c; 
        re=;
        int k=;
        for(c=Get_Char();(c<'0'||c>'9') && c!='-';c=Get_Char());  
        if(c=='-')c=Get_Char(),k=-;
        while(c>='0'&&c<='9')  
            re=(re<<)+(re<<)+(c-'0'),c=Get_Char();  
        re*=k;
    } 
    inline void Rd(char *s)
    {
        char c;
        int len=;
        for(c=Get_Char();c<'A'||c>'z';c=Get_Char()); 
        while(c!=' ' && c!='\n')
            s[len++]=c,c=Get_Char();
    }
    int t[],sz;
    inline void outs(int x)
    {
        sz=;
        do{
            t[++sz]=x%;
            x/=;
        }while(x);
        for(int i=sz;i;i--)putchar(t[i]^);
        putchar('\n');
    }
}
struct TRIE
{
    int rt[maxv],np,ch[maxv][],sz[maxv],val[maxv];
    void Build()
    {
        np=;
        memset(rt,,sizeof(rt));
        memset(ch,,sizeof(ch));
        memset(sz,,sizeof(sz));
        memset(val,,sizeof(val));
        rt[]=;
    }
    int Newnode(int pre)
    {
        ++np;
        if(pre)
            ch[np][]=ch[pre][],ch[np][]=ch[pre][],sz[np]=sz[pre],val[np]=val[pre];
        else
            ch[np][]=ch[np][]=sz[np]=val[np]=;
        return np;
    }
    void add(int pre,int &now,int x,int i)
    {
        now=Newnode(pre);
        sz[now]++;
        if(i>N)
        {
            val[now]++;
            return;
        }
        bool id=x&(<<(N-i));
        add(ch[pre][id],ch[now][id],x,i+);
    }
    void add(int x,int c)
    {
        //cout<<x<<endl;
        int pre=rt[c-];
        int now=rt[c]=Newnode(pre);
        for(int i=;i<=N;i++)
        {
            bool id=x&(<<(N-i));
            ch[now][id]=Newnode(ch[pre][id]);
            sz[ch[now][id]]++;
            now=ch[now][id];
            pre=ch[pre][id];
        }
        val[now]++;
    }
    int query(int lnow,int rnow,int x,int i)
    {
        if(i>N)return ;
        bool id=x&(<<(N-i));
        int ret;
        if(sz[ch[rnow][id^]]-sz[ch[lnow][id^]])
        {
            ret=query(ch[lnow][id^],ch[rnow][id^],x,i+);
            ret=ret|(<<(N-i));
        }
        else
        {
            ret=query(ch[lnow][id],ch[rnow][id],x,i+);
            ret=ret&(~(<<(N-i)));
        }
        return ret;
    }
    int query(int x,int l,int r)
    {
        //cout<<x<<endl;
        int lnow=rt[l],rnow=rt[r];
        for(int i=;i<=N;i++)
        {
            bool id=x&(<<(N-i));
            if(sz[ch[rnow][id^]]-sz[ch[lnow][id^]])
            {
                x=x|(<<(N-i));
                rnow=ch[rnow][id^];
                lnow=ch[lnow][id^];
            }
            else
            {
                x=x&(~(<<(N-i)));
                rnow=ch[rnow][id];
                lnow=ch[lnow][id];
            }

        }
        return x;
    }
}tri;
int n,m;
int sum[maxv];
char s[];
void Init()
{
    int x;
    IStream::Rd(n);IStream::Rd(m);
    tri.Build();
    for(int i=;i<=n;i++)
    {
        IStream::Rd(x);
        sum[i]=sum[i-]^x;
        tri.add(tri.rt[i-],tri.rt[i],sum[i-],);
    }
}
void solve()
{
    int x,l,r;
    while(m--)
    {
        IStream::Rd(s);
        if(s[]=='A')
        {
            n++;
            IStream::Rd(x);
            sum[n]=sum[n-]^x;
            tri.add(tri.rt[n-],tri.rt[n],sum[n-],);
        }
        else
        {
            IStream::Rd(l);IStream::Rd(r);IStream::Rd(x);
            IStream::outs(tri.query(tri.rt[l-],tri.rt[r],x^sum[n],));
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    Init();
    solve();
    return ;
}