CF1100F Ivan and Burgers

Description

求区间最大异或和。

Sol

前置芝士：线性基。

首先最直白的想法就是线段树/ ST 表暴力合并线性基，但这个是的显然gg。

然后还有一个思路是分治处理，但这个是的也挺卡。

于是使用常见套路之离线后排序+扫描线，尝试不断维护当前右端点的所有左端点的答案。

此时发现问题转移到如何保证询问时不会取到超出边界的元素。

考虑对线性基的插入进行一点修改：记录线性基中每个元素在序列中的位置，插入新元素时如果碰到一位是：

如果线性基这一位为空，直接填到这里即可；
如果线性基这一位在原序列中的位置更小，那么将这个数插入到这一位不会更劣，于是把这个数插入到这个位置，原来的数代替这个数向下继续插入。

可以证明这样的贪心是正确的，证明略。

查询的时候如果线性基这一位的大于询问左端点就可以尝试更新答案。

加上排序，时间复杂度。

Code

#include<bits/stdc++.h>
using std::vector;
typedef vector<int> vi;
typedef long long ll;
const int DD=20;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
struct LinerChicken{
    private:
        vector<int> C,P;
    public:
        LinerChicken():C(DD+1),P(DD+1){}
        void ins(int p,int x){
            for(int i=DD;~i;--i)if(x&(1<<i)){
                if(!C[i])return C[i]=x,P[i]=p,void();
                else if(P[i]<p)std::swap(C[i],x),std::swap(P[i],p);
                x^=C[i];
            }
        }
        int qry(int l){
            int ans=0;
            for(int i=DD;~i;--i)if(P[i]>=l)ans=std::max(ans,ans^C[i]);
            return ans;
        }
};
int main(){
    int n=read();
    vi a(n+1);
    for(int i=1;i<=n;++i)a[i]=read();
    int Q=read();
    vector<std::array<int,3>> q(Q+1);
    for(int i=1;i<=Q;++i)q[i][0]=read(),q[i][1]=read(),q[i][2]=i;
    std::sort(q.begin()+1,q.end(),[&](std::array<int,3> x,std::array<int,3> y){return x[1]==y[1]?x[0]<y[0]:x[1]<y[1];});
    LinerChicken C;
    vi ans(Q+1);
    for(int i=1,j=1;i<=n;++i){
        C.ins(i,a[i]);
        for(;j<=Q&&q[j][1]<=i;++j)ans[q[j][2]]=C.qry(q[j][0]);
    }
    for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);
    return 0;
}