【模板】可持久化0/1tire

题目：题目详情 - 最大异或和 - Hydro (v100.vip)

题意：可持久化数据结构，求从l，r区间选一个位置开始，一直异或到最后然后与x进行异或，求最大为多少。

分析：

1. [l,r] 作为起点，N作为终点，那么 r+1~n 的值一定会与x进行异或，是一个定值。提前处理。
2. 要使异或值最大，那肯定是越前的位数就要相反。即建立树的时候从高位开始建。
3. 在1和2的基础上，要使得更快更有效的方法，怎么实现？？？ 前缀和思想 ！！ 建树的时候，建的就是前缀异或和的树， 求答案的时候，就用[ l , r ]区间的值去和 x^s[n]看怎么走异或值最大 如果用s[y]代表前缀异或和的话。那么最大值=s[n]^x^ s ( l , r ) = ( a[1]^a[2]……a[n] ) ^ x ^ ( a[1] ^ a[2] ^ …… ^ a[ (l,r) ] )，求由于s[n]^x为定值，我们只需要从r位置开始求前缀异或和后尽量与s[n]^相反的值就可以了 直接上代码

insert(int x,int y,int i)

插入前缀异或和 x是当前插入的位置编号，y是上一个节点的编号，i是插入的是第几个数（用于判断是否超出范围）

void insert( int x,int y,int i ) 
{  vesion[x]=i; 
   for(int k=len;k>=0;k--) 
   {  int c=s[i]>>k&1; 
      ch[ x ][ !c ]=ch[ y ][ !c ];  //离他本身最近的那个节点但值相反的位置在哪
      ch[ x ][ c ]=++idx; //为自己建节点。
      x=ch[x][c],y=ch[y][c]; 
     vesion[x]=i;  //这个位置是第i个
    } 
}

插入的时候插入前缀异或和，并记录前缀相同的位置

quire( int x,int l,int v )

查询函数，要求最左端不超过l，并且该位置与v异或值相反的最大值。

int quire( int x,int l,int v )
{
  int ans=0;  //记录答案
  for(int k=len;k>=0;k--)  //从高位开始异或
  {
    int c=(v>>k)&1;   //获取这个位置的二进制值
    if( vesion[ch[x][!c]]>=l )  //如果往反方向走没有走出l的位置
      x=ch[x][!c],ans+=1<<k;  //走过去，并且答案增加
    else x=ch[x][c];  //反之走不过去，答案不更新
  }
  return ans;
}

code

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+12,len=23;
int ch[N*25][2],s[N],vesion[N*25],idx,root[N];
void insert( int x,int y,int i )
{
  vesion[x]=i;
  for(int k=len;k>=0;k--)
  {
    int c=s[i]>>k&1;
    ch[ x ][ !c ]=ch[ y ][ !c ];
    ch[ x ][ c ]=++idx;
    x=ch[x][c],y=ch[y][c];
    vesion[x]=i;
  }
}
int quire( int x,int l,int v )
{
  int ans=0;
  for(int k=len;k>=0;k--)
  {
    int c=(v>>k)&1;
    if( vesion[ch[x][!c]]>=l )
      x=ch[x][!c],ans+=1<<k;
    else x=ch[x][c];
  }
  return ans;
}
int n,m;
int main(){
  char p;
  int x,l,r;  
  vesion[0]=-1;
  root[0]=++idx;
  insert(root[0],0,0);
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>x;
    s[i]=s[i-1]^x;
    root[i]=++idx;
    insert( root[i],root[i-1],i );
  }
  while(m--)
  {
    cin>>p;
    if( p=='A' )
    {
      cin>>x;
      n++;
      s[n]=s[n-1]^x;
      root[n]=++idx;
      insert( root[n],root[n-1],n );
    }
    else
    {
      cin>>l>>r>>x;
      cout<<quire( root[r-1],l-1,s[n]^x )<<endl;
    }

  }


}