题解：AT_abc223_h [ABC223H] Xor Query

· · 题解

一道很水的 ABC 压轴题，正好让我从刚刚离开初中的感觉回到了才来初中的感觉。

感觉区分了做过 Ivan and Burgers 和没做过的人。

前缀线性基

就是针对于求静态区间 [l,r] 线性基的一种利器。

前缀线性基仍然维护的是 [1,r] 的线性基，但是除了维护线性基内的值而外，还要维护它来自哪个位置的数。

举个例子，一段区间为 [1,2]，它的线性基为：

\dots & 2 & 1\\ \dots & 2 & 1 \end{matrix}

看起来两行是一样的，其实截然不同。

第一行代表的是普通线性基里面的值，第二行代表它从哪个地方转移而来。

再考虑另外一个例子：[3,2]。

首先插入 3：

\dots & 3 &\dots\\ \dots & 1 &\dots \end{matrix}

接下来插入 2 的时候，我们考虑如果之后查询区间 [2,n]（默认 n 的值很大），按照普通的把 2 与 3 异或得到 1 的思路有问题：可能在需要用位置 2 影响 2^1 数位时，无法发挥其作用。就考虑把 2 放在 2^1 数位上，3 变成 1 放在 2^0 数位上。

组成的线性基又变成了：

\dots & 2 & 1\\ \dots & 2 & 1 \end{matrix}

正常的异或操作要照常进行。

等于是说：保证总体值最大的情况下，尽量把偏后的数放在线性基的高位。

在本题中，l 和 r 都是变化的，所以要储存每一个位置的线性基。

接下来，因为我们搞的到 r 的线性基，所以我们就利用 r 的线性基计算能否凑出 x。

一种有趣的做法是从高位向低位判断，若将目前的数异或上线性基这个位置的数，会使目前的数和 x 异或值变小就异或。注意不要单纯判断与值或者或值的变化。

若之后能把原数变成 x 则可以实现。时间复杂度 O(n\log V+q\log V)。

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

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48); 
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
const int N=4*114514;
int n,q;
int a[N];
int pow2[N];    //处理 2 的次幂  
int xxj[N][70]; //前缀线性基 构造方案跟着发生转变  
int xxj2[N][70];    //记录数所在的位置  
void insert(int sum,int rank,int rank1){
    //前缀线性基 插到真正的空位才停下来 
    //保证高位的 rank 尽量在后面 
    //rank1 代表的是目前的情况  
    for(int i=62;i>=0;i--){
        if(sum>=pow2[i]&&rank>xxj2[rank1][i]){
            int sum2=xxj[rank1][i]; //至关重要！这里的 rank1 存下来就是为了防止在迭代时发生变化。
            int rank2=xxj2[rank1][i];   //记录新的替换下来的数 
            xxj[rank1][i]=sum;
            xxj2[rank1][i]=rank;    //新的线性基记录 
            if(sum2){
                //一个重要条件就是 sum2 真实存在  
                sum=sum2^xxj[rank1][i],rank=rank2;  //遇到新的再插进去即可  
            }
            else{
                sum=0,rank=0;
            } 
        }
        else if(sum>=pow2[i])   sum^=xxj[rank1][i];
    } 
//  for(int i=10;i>=0;i--){
//      cout<<'#'<<i<<' '<<xxj[rank1][i]<<' '<<xxj2[rank1][i]<<endl;
//  }
//  cout<<endl;
}
void solve(int l,int r,int x){
//  for(int i=10;i>=0;i--){
//      cout<<'!'<<i<<' '<<xxj[r][i]<<' '<<xxj2[r][i]<<endl;
//  }
    //接下来要跑的是 [1,r] 的线性基 
    int include13=0;    //这就是目前的数  
    for(int i=62;i>=0;i--){
        if(xxj2[r][i]>=l){
            //一个重要的前提条件就是线性基里面有这个值 
            int now=xxj[r][i];
//          if(((include13^now)&x)>(include13&x)){
//              include13^=now;
//          } 
//          else if(((include13^now)|x)<(include13|x)){
//              include13^=now;
//          }
//          if(((include13^now)|x)<(include13|x)){
//              include13^=now;
//          }
//          else if(((include13^now)&x)>(include13&x)){
//              include13^=now;
//          } 
            if(((include13^now)^x)<(include13^x)){
                include13^=now;
            }
//          cout<<'@'<<now<<' '<<include13<<endl;
        } 
    } 
    if(include13==x)    puts("Yes");
    else    puts("No");
//  putchar('\n');
}
void init(){
    pow2[0]=1;
    for(int i=1;i<=62;i++){
        pow2[i]=pow2[i-1]*2;    //处理 2 的次幂  
    }
} 
signed main(){
    init();
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        for(int j=0;j<=68;j++){
            xxj[i][j]=xxj[i-1][j];  //先把上一个线性基拷贝过来  
            xxj2[i][j]=xxj2[i-1][j];
        }
        a[i]=read();
        insert(a[i],i,i);  
    } 
    while(q--){
        int l=read(),r=read(),x=read(); //先输入若干个数 
        solve(l,r,x); 
    } 
    putchar('\n');
    return 0;
}//信誓旦旦给了承诺 却被时间扑了空