ACM-ICPC 2017 Asia Xi'an A XOR （线性基+线段树思想）

题目链接

题意;给个数组，每次询问一个区间你可以挑任意个数的数字异或和 然后在或上k的最大值

题解：线性基不知道的先看这个，一个线性基可以log的求最大值把对应去区间的线性基求出来然后用线段树维护线性基

 

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 100009
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
int read()
{
    char ch=' ';
    int ans=0;
    while(ch<'0' || ch>'9')
        ch=getchar();
    while(ch<='9' && ch>='0')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
struct ac{
   int a[50];
   void init(){
      memset(a,0,sizeof(a));
   }
   bool add(int x){
       for(int j=30;j>=0;j--){
          if(x&(1<<j)){
             if(!a[j]){
                a[j]=x;
                break;
             }
             x^=a[j];
          }
       }
       return x>0;
   }
   int query(){
      int x=0;
      for(int j=30;j>=0;j--){
         if((x^a[j])>x){
            x^=a[j];
         }
      }
      return x;
   }
   ac merge_LB(ac x){
        ac ret;
        for(int i=0;i<=30;i++){
            ret.a[i]=a[i];
        }
        for(int i=0;i<=30;i++){
            ret.add(x.a[i]);
        }
        return ret;
   }
}tre[maxn*10];
int b[maxn];
void build(int l,int r,int in){
  tre[in].init();
  if(l==r){
    tre[in].add(b[l]);
    return ;
  }
  int mid=(l+r)/2;
  build(l,mid,in*2);
  build(mid+1,r,in*2+1);
  tre[in]=tre[in*2].merge_LB(tre[in*2+1]);
}
ac query(int l,int r,int x,int y,int in){
   if(l==x&&r==y){
        return tre[in];
    }
    int mid=(x+y)/2;
    //ac ret;ret.init();
    if(r<=mid) return(query(l,r,x,mid,in*2));
    else if(l>mid)  return(query(l,r,mid+1,y,in*2+1));
    return query(l,mid,x,mid,in*2).merge_LB(query(mid+1,r,mid+1,y,in*2+1));
}
int main(){
   int t;
   cin>>t;
   while(t--){
      int n,m,k;
     //scanf("%d%d%d",&n,&m,&k);
      n=read();m=read();k=read();
      k=~k;
      for(int j=1;j<=n;j++){
         scanf("%d",&b[j]);
         b[j]&=k;
      }
      k=~k;
      build(1,n,1);
      for(int j=0;j<m;j++){
          int l,r;
          //scanf("%d%d",&l,&r);
          l=read();r=read();
          ac ans=query(l,r,1,n,1);
          int an=ans.query();
          an|=k;
          printf("%dn",an);
      }
   }
}