【Ynoi2013】无力回天NOI2017

mrsrz 11月 04, 2019

线段树维护线性基

题目大意：

给定一个数列，有两个操作：

给定 $l,r,v$，令位置在 $[l,r]$ 内的所有数都异或上 $v$。
给定 $l,r,v$，从位置在 $[l,r]$ 内的数中选取任意个（可以不选），依次和 $v$ 异或起来，求异或最大值。

题解：

考虑第二个操作，很容易想到用线段树+线性基维护。但是区间修改操作，每次会对整个区间的数进行修改，没有办法快速重构出一个线性基。

令原数列为 $a_{1..n}$，再定义一个数列为 $b_{1..n}$，其中 $b_i(i>1)=a_{i}\oplus a_{i-1}$，$b_1$ 的值可以不用管。

考虑数列 $b$ 的优秀性质。

由于异或运算的美妙性质 $A\oplus B\oplus B=A$，我们进行区间异或的时候，在 $b$ 数组上只会修改两个数的值。那么维护 $b$ 的区间线性基就非常容易。

考虑 $b$ 的线性基的特点。

我们发现，如果我们有 $a_i,b_{i+1},b_{i+2},\dots,b_k$，它的线性基和 $a_{i},a_{i+1},a_{i+2},\dots,a_k$ 的线性基是等价的。因为 $b_{i+1}\oplus a_{i}=a_{i+1},b_{i+2}\oplus a_{i+1}=a_{i+2}$，即可以通过有限次异或操作还原原数列。

那么我们只需要对每次查询，在线段树上查询 $b_{l+1..r}$ 的线性基，然后插入 $a_l$ 元素即可。

然后把 $v$ 扔进这个线性基里跑最大值就好了。

这里还要维护原来的 $a_i$ 的值，区间异或单点查询，随便搞搞就好了。

时间复杂度 $O(n\log^3 n)$，空间复杂度 $O(n\log n)$。有更优秀的复杂度。

一个小优化：如果线性基里已经插满，那么我们不需要每次 $O(\log^2 n)$ 合并。在较为随机的数据下有很好的效果。

Code：

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+7;
int n,m;
int d[N],a[N/4],b[N/4];
struct Base{
    int sz,a[30];
    inline Base():sz(0){memset(a,0,sizeof a);}
    inline Base&operator+=(int b){
        if(sz==30||!b)return*this;
        for(int i=29;~i;--i)
            if(b>>i&1){
                if(!a[i]){
                    a[i]=b,++sz;
                    return*this;
                }
                b^=a[i];
            }
        return*this;
    }
    inline Base operator*(const Base&rhs)const{
        if(sz==30)return*this;
        if(rhs.sz==30)return rhs;
        Base ret=*this;
        for(int i=29;~i;--i)if(rhs.a[i])ret+=rhs.a[i];
        return ret;
    }
    inline int operator()(int v){
        for(int i=29;~i;--i)if((v^a[i])>v)v^=a[i];
        return v;
    }
}G[N];
void modify(int l,int r,int o,const int&L,const int&R,const int&v){
    if(L<=l&&r<=R)d[o]^=v;else{
        const int mid=l+r>>1;
        if(L<=mid)modify(l,mid,o<<1,L,R,v);
        if(mid<R)modify(mid+1,r,o<<1|1,L,R,v);
    }
}
int query(int l,int r,int o,const int&pos){
    if(l==r)return d[o];
    const int mid=l+r>>1;
    return d[o]^(pos<=mid?query(l,mid,o<<1,pos):query(mid+1,r,o<<1|1,pos));
}
void build(int l,int r,int o){
    if(l==r)cin>>d[o],a[l]=d[o];else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
    }
}
void build_(int l,int r,int o){
    if(l==r)G[o]+=b[l]=a[l]^a[l-1];else{
        const int mid=l+r>>1;
        build_(l,mid,o<<1);
        build_(mid+1,r,o<<1|1);
        G[o]=G[o<<1]*G[o<<1|1];
    }
}
void modify_(int l,int r,int o,const int&pos,const int&val){
    if(l==r)G[o]=G[0],G[o]+=b[l]^=val;
    else{
        const int mid=l+r>>1;
        if(pos<=mid)modify_(l,mid,o<<1,pos,val);else modify_(mid+1,r,o<<1|1,pos,val);
        G[o]=G[o<<1]*G[o<<1|1];
    }
}
Base query_(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return G[o];
    const int mid=l+r>>1;
    if(L<=mid&&mid<R)return query_(l,mid,o<<1,L,R)*query_(mid+1,r,o<<1|1,L,R);
    if(L<=mid)return query_(l,mid,o<<1,L,R);return query_(mid+1,r,o<<1|1,L,R);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    build(1,n,1);
    build_(1,n,1);
    while(m--){
        int op,l,r,v;
        cin>>op>>l>>r>>v;
        if(op==1){
            modify(1,n,1,l,r,v);
            modify_(1,n,1,l,v);
            if(r!=n)modify_(1,n,1,r+1,v);
        }else{
            Base s=(l==r?G[0]:query_(1,n,1,l+1,r));
            s+=query(1,n,1,l);
            cout<<s(v)<<'\n';
        }
    }
    return 0;
}