发布时间：2024-07-31

前缀线性基

struct PrefixLinearBasis{
    vector<int> d,pos;
    static constexpr int SIZE=20;
    PrefixLinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        pos.assign(SIZE,-1);
    }
    bool insert(int x,int p){
        for(int i=SIZE-1;~i;i--){
            if(!(x>>i&1))continue;
            if(d[i]){
                if(pos[i]<p){
                    swap(pos[i],p);
                    swap(d[i],x);
                }
                x^=d[i];
            }
            else{
                d[i]=x;
                pos[i]=p;
                return true;
            }
        }
        return false;
    }
    int query_max(int l=0){
        int ans=0;
        for(int i=SIZE-1;~i;i--){
            if(pos[i]>=l)ans=max(ans,ans^d[i]);
        }
        return ans;
    }
};