最大异或和

可持久化Trie

题面

给定一个初始长度为$N$的非负整数序列$\{a\}$。
有$m$个操作，操作分为两种：

• 在序列末尾加一个数，$++N$

• 给出$l,r,x$，找出满足$l\leq p\leq r$的位置$p$,最大化$a_p\bigoplus a_{p+1}\bigoplus a_{p+2}\bigoplus...\bigoplus a_{N}\bigoplus x$。

• $n\leq3*10^5,a_i\leq10^7$

解析

维护区间最大异或和当然要召唤可持久化$Trie$树啦。
它的功能是，在完成建树后，能在给定一段区间和一个数的情况下得出它们异或得到的最大值。

具体建立方法有点像把$Trie$树和主席树结合起来。
插入一个数（新建一棵树），枚举到某一位时，若这个数这一位是$p$，则只用递归处理$p$子树，$p\bigoplus1$子树可以使用前面已有的对应子树。
对于询问，递归时若$x$这一位为$p$，则把$r$树和$l-1$树对应子树(能贡献答案的)大小作差，若差为$0$，说明区间中不存在该位为$p\bigoplus1$的数，答案该位为$0$。依此类推。
（其实看代码最清楚）

至于这个奇怪的询问方式，设异或前缀和为$S$，则询问可视为$S_N\bigoplus S_{p-1}$。

注意数组$rt,sum,t$等数组大小要开到$n*50$左右。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=3e7+100;
int n,m,tot,sum[N],t[N][2],rt[N],tim;
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il void Build(re int x,re int &y,re int w,re int d)
{
  sum[y=++tim]=sum[x]+1;
  if(d<0) return;
  re int tmp=(w>>d)&1;
  t[y][tmp^1]=t[x][tmp^1];
  Build(t[x][tmp],t[y][tmp],w,d-1);
}
il int Query(re int x,re int y,re int w,re int d)
{
  if(d<0) return 0;
  re int tmp=(w>>d)&1,p=sum[t[y][tmp^1]]-sum[t[x][tmp^1]];
  if(p>0) return (1<<d)+Query(t[x][tmp^1],t[y][tmp^1],w,d-1);
  else return Query(t[x][tmp],t[y][tmp],w,d-1);
}
int main()
{
  n=gi();m=gi();
  Build(rt[0],rt[1],0,25);++n;
  fp(i,2,n)
    {
      re int x=gi();tot^=x;
      Build(rt[i-1],rt[i],tot,25);
    }
  while(m--)
    {
      re char s[5];scanf("%s",s);
      if(s[0]=='A')
    {
      re int x=gi();tot^=x;
      Build(rt[n],rt[n+1],tot,25);++n;
    }
      else
    {
      re int l=gi(),r=gi(),x=gi();
      printf("%d\n",Query(rt[l-1],rt[r],tot^x,25));
    }
    }
  return 0;
}