最大異或和 HYSBZ - 3261

https://www.lydsy.com/JudgeOnline/problem.php?id=3261

可持久化字典樹存模闆 和主席樹差不多 每次更新動态開點

題目查詢的是某個異或字尾 利用異或自反性 把字首插入樹中 查字尾就異或整個區間即可

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

struct node
{
    int c[2];
    int sum;
};

node tree[15000010];
int a[600010],b[600010],root[600010];
int bin[50];
int n,q,num;

void init()
{
    int i;
    bin[0]=1;
    for(i=1;i<=30;i++) bin[i]=2*bin[i-1];
}

int update(int rot,int val)
{
    int res,cur,i,id;
    res=cur=num++;
    for(i=24;i>=0;i--)
    {
        //c[cur][0]=c[rot][0];
        //c[cur][1]=c[rot][1];
        //sum[cur]=sum[rot]+1;
        tree[cur]=tree[rot];
        tree[cur].sum++;
        id=val&bin[i];
        id>>=i;
        //c[cur][id]=num++;
        //cur=c[cur][id];
        //rot=c[rot][id];
        tree[cur].c[id]=num++;
        cur=tree[cur].c[id];
        rot=tree[rot].c[id];
    }
    tree[cur]=tree[rot];
    tree[cur].sum++;
    return res;
}

int query(int lrot,int rrot,int val)
{
    int res,i,id;
    res=0;
    for(i=24;i>=0;i--)
    {
        id=val&bin[i];
        id>>=i;
        if(tree[tree[rrot].c[id^1]].sum-tree[tree[lrot].c[id^1]].sum>0) res+=bin[i],lrot=tree[lrot].c[id^1],rrot=tree[rrot].c[id^1];
        else lrot=tree[lrot].c[id],rrot=tree[rrot].c[id];
    }
    return res;
}

int main()
{
    int i,tmp,val,l,r;
    char op[10];
    init();
    scanf("%d%d",&n,&q);
    tmp=0,n++,num++;
    root[1]=update(root[0],tmp);
    for(i=2;i<=n;i++)
    {
        scanf("%d",&val);
        tmp^=val;
        root[i]=update(root[i-1],tmp);
    }
    while(q--)
    {
        scanf("%s",op);
        if(op[0]=='A')
        {
            n++;
            scanf("%d",&val);
            tmp^=val;
            root[n]=update(root[n-1],tmp);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&val);
            printf("%d\n",query(root[l-1],root[r],val^tmp));
        }
    }
    return 0;
}