[ [Ynoi2013] 无力回天 NOI2017 ] 解题报告

[Ynoi2013] 无力回天 NOI2017

首先看到异或，想到能维护异或的东西就那几样（线性基/01trie/数位 dp/FWT），再看到求选任意个数后的异或最大值，线性基无疑了。

这时再看还要维护什么其它信息，区间异或，区间查询，一副线段树维护线性基的样子。但我们知道线性基中的值一旦修改就必须重构，区间修改的时间复杂度不允许，尝试优化这个做法。

可以发现虽然不允许区间修改，但允许单点修改。区间转单点，想到了什么？差分！考虑令 \(b\) 表示原数组的异或差分数组，即 \(b_i=\begin{cases}a_i&\text{若}\ i=1\\a_{i-1}\oplus a_i&\text{若}\ i\not=1\end{cases}\)。反过来，\(a_i\) 为 \(b\) 的异或前缀和。可以发现每次区间异或操作相当于修改 \(b_l\) 和 \(b_{r+1}\) 两个值。

又因为若线性基中的数能表示 \(a_{i-1}\)，那么再插入一个 \(b_i\) 一定能够表示 \(a_i\)。所以 \(\{a_l,a_{l+1},a_{l+2},\dots,a_r\}\) 的线性基等价于在 \(\{b_{l+1},b_{l+2},\dots,b_r\}\) 的线性基中插入 \(a_l\) 后的线性基。因此用线段树维护 \(b_l,b_{l+1},b_{l+2},\dots,b_r\) 的线性基，每次修改操作重构 \(l\) 和 \(r+1\) 处的线性基即可。复杂度 \(O(n\log^3n)\)

点击查看代码

#include<bits/stdc++.h>

#define ull unsigned long long

#define ll long long

#define pdi pair<double,int>

#define pii pair<int,int>

#define pb push_back

#define mp make_pair

#define eps 1e-9

using namespace std;

namespace IO{

    template<typename T>

    inline void read(T &x){

        x=0;

        int f=1;

        char ch=getchar();

        while(ch>'9'||ch<'0'){

            if(ch=='-'){

                f=-1;

    }

            ch=getchar();

        }

        while(ch>='0'&&ch<='9'){

            x=x*10+(ch-'0');

            ch=getchar();

        }

        x=(f==1?x:-x);

    }

    template<typename T>

    inline void write(T x){

        if(x<0){

            putchar('-');

            x=-x;

        }

        if(x>=10){

            write(x/10);

        }

        putchar(x%10+'0');

    }

    template<typename T>

    inline void write_endl(T x){

        write(x);

        putchar('\n');

    }

    template<typename T>

    inline void write_space(T x){

        write(x);

        putchar(' ');

    }

}

using namespace IO;

const int N=5e4+10,Lg=30;

int a[N],b[N],n,q;

struct base{

    int p[35];

    void ins(int &x){

        for(int i=Lg;i>=0;i--){

            if(x>>i&1){

                if(!p[i]){

                    p[i]=x;

                    break;

                }

                else{

                    x^=p[i];

                }

            }

        }

    }

    void clear(){

        for(int i=Lg;i>=0;i--){

            p[i]=0;

        }

    }

    int query(int mx){

        for(int i=Lg;i>=0;i--){

            if((mx^p[i])>=mx){

                mx^=p[i];

            }

        }

        return mx;

    }

};

base merge(base x,base y){

    for(int i=Lg;i>=0;i--){

        x.ins(y.p[i]);

    }

    return x;

}

namespace Seg_Tree{

    base ans[N<<2];

    #define ls(p) p<<1

    #define rs(p) p<<1|1

    void push_up(int p){

        ans[p]=merge(ans[ls(p)],ans[rs(p)]);

    }

    void build(int p,int l,int r){

        if(l==r){

            ans[p].ins(b[l]);

            return;

        }

        int mid=(l+r)>>1;

        build(ls(p),l,mid);

        build(rs(p),mid+1,r);

        push_up(p);

    }

    void update(int p,int l,int r,int pos,int val){

        if(l==r){

            ans[p].clear();

            b[l]^=val;

            ans[p].ins(b[l]);

            return;

        }

        int mid=(l+r)>>1;

        if(pos<=mid){

            update(ls(p),l,mid,pos,val);

        }

        else{

            update(rs(p),mid+1,r,pos,val);

        }

        push_up(p);

    }

    base query(int p,int l,int r,int q_l,int q_r){

        if(q_l<=l&&r<=q_r){

            return ans[p];

        }

        int mid=(l+r)>>1;

        if(q_r<=mid){

            return query(ls(p),l,mid,q_l,q_r);

        }

        if(q_l>mid){

            return query(rs(p),mid+1,r,q_l,q_r);

        }

        return merge(query(ls(p),l,mid,q_l,q_r),query(rs(p),mid+1,r,q_l,q_r));

    }

}

namespace Fenwick_Tree{

    int ans[N];

    int lowbit(int x){

        return x&(-x);

    }

    void update(int pos,int val){

        while(pos<=n){

            ans[pos]^=val;

            pos+=lowbit(pos);

        }

    }

    int query(int pos){

        int res=0;

        while(pos){

            res^=ans[pos];

            pos-=lowbit(pos);

        }

        return res;

    }

}

signed main(){

    #ifndef ONLINE_JUDGE

        freopen("1.in","r",stdin);

        freopen("1.out","w",stdout);

    #endif

    read(n),read(q);

    for(int i=1;i<=n;i++){

        read(a[i]);

        b[i]=a[i]^a[i-1];

    }

    Seg_Tree::build(1,1,n);

    for(int i=1;i<=n;i++){

        Fenwick_Tree::update(i,b[i]);

    }

    while(q--){

        int opt,l,r,val;

        read(opt),read(l),read(r),read(val);

        if(opt==1){

            Seg_Tree::update(1,1,n,l,val);

            Fenwick_Tree::update(l,val);

            if(r<n){

                Seg_Tree::update(1,1,n,r+1,val);

                Fenwick_Tree::update(r+1,val);

            }

        }

        else{

            int x=Fenwick_Tree::query(l);

            base y;

            y.clear();

            if(l!=r){

                y=Seg_Tree::query(1,1,n,l+1,r);

            }

            y.ins(x);

            write_endl(y.query(val));

        }

    }

    return 0;

}

[ [Ynoi2013] 无力回天 NOI2017 ] 解题报告