【BZOJ 3261】最大异或和【可持久化字典树】

题意

给出一个长度为n的整数序列，给出m个操作。操作有两种。1，Ax表示在序列结尾增加x。2，Qlrx表示找到一个位置p满足 l<=p<=r，使得a[p] xor a[p+1]xor...xor a[n] xor x最大，并输出这个最大值。

分析

　今天学可持久化字典树的时候的找的一道模板题。对于这个题目其实只要学过主席树应该都能自己写出来(我照着主席树的套路写然后debug一下午然后发现num数组想错了mmp)

我们定义sum[i]为a[1]xor a[2] xor ...xor a[i]。那么对于每个询问操作Qlrx，我们要找出一个[l,r]内的p使得sum[n]xor sum[p-1] xor x最大.而显然sum[n]xor x是一个常数，所以我们要找到一个p使得sum[p-1]xor某个常数最大。

字典树的经典用法就是在一堆数字中，查询某个与x异或最大的是哪个数字。但是这个问题中有区间限制，所以我们需要将其可持久化。与线段树一样，我们记录每个历史版本，也就是前i个数字组成的字典树，根为root[i]。建树的思路和主席树几乎是完全一样的。只不过我们为了实现查询，多更新了一个num数组。因为主席树查询时候可以直接相减得到这个区间内各个数的数量，但是字典树不行，所以我们多维护一个num，来确定在[l,r]区间内，这个节点有没有走向0或者1的方法。

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int maxn=*;

 int n,m,sz;

 int ch[maxn][],a[maxn],root[maxn],sum[maxn],val[maxn],num[maxn][];

 void update(int x,int y,int aa,int id){

     root[x]=++sz;

     x=root[x];

     for(int i=;i>=;i--){

         int c=(aa>>i)&;

         num[x][c]+=num[y][c]+;

         num[x][!c]=num[y][!c];

         ch[x][!c]=ch[y][!c];

         ch[x][c]=++sz;

         memset(ch[sz],,sizeof(ch[sz]));

         x=ch[x][c],y=ch[y][c];

     }

     val[x]=id;

 }

 int query(int x,int y,int aa){

     for(int i=;i>=;i--){

         int c=(aa>>i)&;

         if(num[x][!c]-num[y][!c])

             x=ch[x][!c],y=ch[y][!c];

         else

             x=ch[x][c],y=ch[y][c];

     }

     return val[x];

 }

 int main(){

     scanf("%d%d",&n,&m);

     sz=;

     sum[]=;

     update(,,,);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         sum[i]=sum[i-]^a[i];

         update(i,root[i-],sum[i],i);

     }

     char c;

     int l,r,x;

     for(int i=;i<=m;i++){

         scanf(" %c",&c);

         if(c=='A'){

             n++;

             scanf("%d",&a[n]);

             sum[n]=sum[n-]^a[n];

             update(n,root[n-],sum[n],n);

         }else{

             scanf("%d%d%d",&l,&r,&x);

             printf("%d\n",sum[query(root[r-],root[l-],x^sum[n])]^sum[n]^x);

         }

     }

 return ;

 }

 //LQL

巴特西

【BZOJ 3261】最大异或和【可持久化字典树】

最新文章

热门文章