题解 CF1100F 【Ivan and Burgers】

· · 题解

题意

给定一组数a，有q组询问求a_l\to a_r的异或最大值

题解

这是一道前缀线性基的板子题

我们的前缀线性基需要两个变量：p[i]表示第i位的值，pos[i]表示对第i位造成影响的数的编号。那么很显然，假如我们已经求出了1\to r的线性基，其中所有pos≥l的数构成的线性基就是区间[l,r]的数构成的线性基

根据贪心的思想，我们知道，我们要尽可能地让pos[i]的值最大，这样才能保证我们通过上述方法构造出的线性基是[l,r]的线性基

那么如何保证pos[i]的值最大呢？

很简单，如果我们插入一个值x，它的位置为w，那么如果有一位的pos<w，那么我们就把这一位的p取出来换成x，pos换成w，然后把pos,p 继续往下插入，这样构造出的线性基pos就是最大的

代码

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;char c=getchar();bool f=false;
    for(;!isdigit(c);c=getchar())f!=c=='-';
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    if(f)x=-x;
}
template<typename T ,typename ...Arg>
inline void read(T &x,Arg &...args){
    read(x);read(args...);
}
template<typename T>
inline void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
typedef long long ll;
const int max_wei=30;
const int maxn=500000+10;
struct Prefix_Linear_Basis{
    ll p[max_wei+1];int pos[max_wei+1];
    inline void init(){memset(p,0,sizeof p);memset(pos,0,sizeof pos);}
    inline void insert(Prefix_Linear_Basis A,int w,ll val){
        *this=A;
        for(int i=max_wei;i>=0;i--)if(val>>i&1){
            if(!p[i]){p[i]=val,pos[i]=w;return;}
            else if(pos[i]<w){swap(pos[i],w);swap(p[i],val);}
            val^=p[i];
        }
    }
    inline ll Query(int l){
        //查询此基中所有≥l的最大值
        ll ans=0;
        for(int i=max_wei;i>=0;i--)
            if(p[i]&&pos[i]>=l)ans=max(ans,ans^p[i]);
        return ans; 
    }
}a[maxn];
int n,q,x,l,r;
signed main(){
    read(n);a[0].init();
    for(int i=1;i<=n;i++)
        read(x),a[i].insert(a[i-1],i,x);
    read(q);
    while(q--){
        read(l,r);
        write(a[r].Query(l));
        putchar('\n');
    }
}