BZOJ 3261: 最大異或和

這個題，用的可持久化字典樹來維護區間異或和

感覺用法跟主席樹差不多，會主席樹，可持久化字典樹應該不難學

記 res[i] 為 [1 , i ] 的 a[] (程式中我使用的是ans[]) 的異或和

則求max(res[p]res[n]x) (l-1<=p<=r-1)

每次加點将trie樹的這條鍊的權都+1

修改當然是建立一個結點

然後查詢的時候判斷一個結點存在，隻要做區間減法判權是否非0

即若 trie[r].size - trie[l-1].size =0則該結點不存在

查詢的貪心政策,其實很簡單，res[n]^x的二進制某個位置 ind 為1，我們就找可持久化字典樹區間對應位置是否存在0，存在，則這個位置的異或值為1 << ind，不存在0就隻能選擇1（因為這個區間肯定是有數的），是以這個位置的異或值為0，如果位置ind是0的話，相反即可。

#include<cstdio>
using namespace std;

const int maxn=600000+100;

struct Trie{
  
  int l,r;
  int size;
}trie[maxn*24];
int tot,root[maxn];
int ans[maxn],res[maxn];

inline void Update(int &New,int Old,int v){
  
  New=++tot;
  trie[New]=trie[Old];
  trie[New].size=trie[Old].size+1;
  int now=New,pre=Old;
  for(int i=24;i>=0;i--){
    
    int tmp=(v>>i)&1;
    int nodel=trie[pre].l,noder=trie[pre].r;
    if(tmp){
      
      trie[now].l=nodel;
      trie[now].r=++tot;
      trie[tot]=trie[noder];
      trie[tot].size=trie[noder].size+1;
      now=tot,pre=noder;
    }
    else{
      
      trie[now].r=noder;
      trie[now].l=++tot;
      trie[tot]=trie[nodel];
      trie[tot].size=trie[nodel].size+1;
      now=tot,pre=nodel;
    }
  }
}

inline int Query(int l,int r,int v){
  
  int query=0;
  if(l<0) l=0;
  for(int i=24;i>=0;i--){
    
    int Lnodel=trie[l].l,Lnoder=trie[l].r;
    int Rnodel=trie[r].l,Rnoder=trie[r].r;
    int tmp=(v>>i)&1;
    if(tmp){
      
      if(trie[Rnodel].size-trie[Lnodel].size) query+=(1<<i),l=Lnodel,r=Rnodel;
      else  l=Lnoder,r=Rnoder; 
    }
    else{
      
      if(trie[Rnoder].size-trie[Lnoder].size) query+=(1<<i),l=Lnoder,r=Rnoder;
      else  l=Lnodel,r=Rnodel; 
    }
  }
  return query;
} 

int main(){
  
  int n,m;
  scanf("%d%d",&n,&m);
  Update(root[0],root[0],0);
  for(int i=1;i<=n;i++){
    
    scanf("%d",&ans[i]);
    res[i]=res[i-1]^ans[i];
    Update(root[i],root[i-1],res[i]);
  }
  while(m--){
    
    char ch=getchar();
    while(ch<'A' || ch>'Z') ch=getchar();
    if(ch=='A'){
      
      n++;
      scanf("%d",&ans[n]);
      res[n]=res[n-1]^ans[n];
      Update(root[n],root[n-1],res[n]);
    }
    else{
      
      int l,r,x;
      scanf("%d%d%d",&l,&r,&x);
      printf("%d\n",Query(root[l-2],root[r-1],res[n]^x));
    }
  }
}