发布时间：2024-07-31

区间线性基(单点插入，区间查询，猫树分治法，前缀线性基)($O(n\log n \log V +m \log^2V)$)

struct PrefixLinearBasis{
    vector<int> d,pos;
    static constexpr int SIZE=35;
    PrefixLinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        pos.assign(SIZE,-1);
    }
    bool insert(int x,int p,int lim){
        for(int i=SIZE-1;~i;i--){
            if(!(x>>i&1))continue;
            if(d[i]){
                if(abs(p-lim)<abs(pos[i]-lim)){
                    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;
    }
};
struct Node{
    int l,r;
    PrefixLinearBasis lb;
} t[N<<2];
void build(int p,int l,int r){
    t[p]={l,r};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void modify(int p,int x,int val){
    if(p>1){
        if(p&1)t[p].lb.insert(val,x,-INF);
        else t[p].lb.insert(val,x,INF);
    }
    if(t[p].l==t[p].r)return;
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)modify(p<<1,x,val);
    else modify(p<<1|1,x,val);
}
int query(int p,int l,int r,int val=0){
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid&&r>=mid){
        PrefixLinearBasis lb;
        for(int i=0;i<lb.SIZE;i++){
            if(t[p<<1].lb.pos[i]>=l&&t[p<<1].lb.pos[i]<=r)lb.insert(t[p<<1].lb.d[i],0,0);
            if(t[p<<1|1].lb.pos[i]>=l&&t[p<<1|1].lb.pos[i]<=r)lb.insert(t[p<<1|1].lb.d[i],0,0);
        }
        return lb.query_max(val);
    }
    if(l<=mid)return query(p<<1,l,r,val);
    return query(p<<1|1,l,r,val);
}