可持久化字典树【模板】

可持久化字典树

P4735 最大异或和

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

const int maxn=6e5+10;
int n,m,sum[maxn],x,l,r,cnt=0;
int ch[maxn*25][2],ver[maxn*25],root[maxn];
//ch表示字典树数组，ver表示每个接节点的版本（第几个字典树），root表示每个点所在的那个字典树的根
char s;

void add(int nw,int pre,int x){//压入当前的根nw，上一个字典树的根pre，这个字典树的编号
  ver[nw]=x;
  for(int i=23;i>=0;i--){
  	int c=(sum[x]>>i)&1;
    ch[nw][!c]=ch[pre][!c];
    ch[nw][c]=++cnt;
    nw=ch[nw][c];pre=ch[pre][c];
    ver[nw]=x;
  }
}

int query(int nw,int limit,int val){//当前字典树的根nw，下限limit，所异或的值val
  int res=0;
  for(int i=23;i>=0;i--){
    int c=(val>>i)&1;
    if(ver[ch[nw][!c]]>=limit) nw=ch[nw][!c],res+=(1<<i);
    else nw=ch[nw][c];
  }
  return res;
}

int main(){
  /*2023.5.1 hewanying P4735 最大异或和 可持久化字典树*/ 
  scanf("%d%d",&n,&m);
  ver[0]=-1;
  root[0]=++cnt;
  add(root[0],0,0);
  for(int i=1;i<=n;i++){
  	scanf("%d",&x);
  	root[i]=++cnt;
  	sum[i]=sum[i-1]^x;
  	add(root[i],root[i-1],i);
  }
  for(int i=1;i<=m;i++){
    scanf(" %c",&s);
    if(s=='A'){
      scanf("%d",&x);
      root[++n]=++cnt;
	  sum[n]=sum[n-1]^x;
      add(root[n],root[n-1],n);
	}
	else{
	  scanf("%d%d%d",&l,&r,&x);
	  printf("%d\n",query(root[r-1],l-1,x^sum[n]));
	}
  }
  return 0;
}