bzoj 3261 最大异或和 可持久化字典树（01树）

题目传送门

思路：

　　由异或的性质可得，题目要求的式子可以转化成求$max(pre[n]^x^pre[i])$，$pre[i]$表示前缀异或和，那么我们现在就要求出这个东西，所以用可持久化字典树来求，每次贪心的往相反的方向看是否有值，具体看代码即可，模板题，注意最好先插入一个0，查询区间的$(l,r)$也要注意一下端点，记住我们要的是前缀。

#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

typedef long long ll;

using namespace std;

const int maxn=;

int sum[maxn*],tr[maxn*][],cnt,root[maxn];

int pre,n,m,l,r,d[];

void split(int x)

{

    int len=;

    while(x>){

        d[len++]=x%;

        x/=;

    }

    while(len<)d[len++]=;

}

inline void update(int &rt,int las){

    sum[rt=++cnt]=sum[las]+;

    int tmp=rt;

    for(int i=;i>=;i--){

        tr[tmp][d[i]^]=tr[las][d[i]^];

        tr[tmp][d[i]]=++cnt,las=tr[las][d[i]];

        sum[tmp=cnt]=sum[las]+;

    }

}

int query(int l,int r){

    int ans=;

    for(int i=;i>=;i--)

    {

        if(sum[tr[r][d[i]^]]-sum[tr[l][d[i]^]]>){

            ans|=(<<i);

            r=tr[r][d[i]^],l=tr[l][d[i]^];

        }else{

            r=tr[r][d[i]],l=tr[l][d[i]];

        }

    }

    return ans;

}

int main(){

    while(cin>>n>>m)

    {

        pre=;

        split();

        update(root[],root[]);

        n++;

        for(int i=;i<=n;i++)

        {

            int x;

            scanf("%d",&x);

            pre^=x;

            split(pre);

            update(root[i],root[i-]);

        }

        char op[];

        for(int i=;i<=m;i++)

        {

            scanf("%s",op);

            if(op[]=='A'){

                n++;

                int x;

                scanf("%d",&x);

                pre^=x;

                split(pre);

                update(root[n],root[n-]);

            }else{

                int l,r,x;

                scanf("%d%d%d",&l,&r,&x);

                split(pre^x);

                printf("%d\n",query(root[l-],root[r]));

            }

        }

    }

}