题解：P17146 [ICPC 2017 Xi'an R] XOR

· · 题解

P17146 [ICPC 2017 Xi'an R] XOR 题解。

题目大意：给你一个序列，每次询问一个区间，允许从区间里挑选若干个元素，求这些元素的异或值再与 k 按位或的最大值。

前置内容：线性基，线段树。

我们可以先不考虑 k，本质就是把线性基塞到线段树上，每次查询区间异或最大值，这样就和这一题类似。

那么怎么处理 k 呢？可以在插入线性基前先对每个数和 \sim k 按位与，实际就是屏蔽掉 k 为 1 的二进制位。在查询后再和 k 按位或即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=101010,BASE=60;
ll t;
ll n,q,k;
ll x;
ll l,r;
struct segtr{
    ll p[61];
    int ps[61];
    segtr(){
        memset(p,0,sizeof(p));
        memset(ps,0,sizeof(ps));
    }
}tree[MAXN];
void insert(segtr &u,ll x,int id){
    for(int i=BASE;i>=0;i--){
        if(!(x>>i&1)) continue;
        if(!u.p[i]){
            u.p[i]=x;
            u.ps[i]=id;
            break;
        }
        if(u.ps[i]<id){
            swap(u.p[i],x);
            swap(u.ps[i],id);
        }
        x^=u.p[i];
    }
}
ll query(const segtr &u,int l){
    ll r=0;
    for(int i=BASE;i>=0;--i){
        if(u.ps[i]>=l && (r^u.p[i])>r) r^=u.p[i];
    }
  //线性基求最大
    return r;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>q>>k;
        memset(tree[0].p,0,sizeof(tree[0].p));
        memset(tree[0].ps,0,sizeof(tree[0].ps));
        for(int i=1;i<=n;i++){
            cin>>x;
            x&= ~(ll)k;//预处理
            tree[i]=tree[i-1];
            insert(tree[i],x,i);
        }
        while(q--){
            cin>>l>>r;
            cout<<(query(tree[r],l)|k)<<'\n';//查询后按位或k
        }
    }
}