Operation--2019杭电多校训练第一场-B题

题目传送门

题目大意为：

给你一个1~n的数组,然后有m个操作，0操作为在数组最后添加一个新元素，1操作为查询区间 [l,r] 子集异或最大值。

其中输入经过加密操作，需要经过解密才能获取正确数据（强制在线）

看到了子集异或值就应该知道是使用线性基的知识。

如果按照暴力的解法一定会超时，但是我们可以通过一定贪心策略找到当前的最优解。

（下面就需要对线性基有清晰的认识了）

添加元素

对于区间[1,x](1 \leq x \leq n)，我们可以通过继承的方式找到每个区间的线性基：

for(int j=30;j>=0;j--){
    f[i][j]=f[i-1][j];//将上一个区间[1,i-1]的线性基继承到[1,i]
    pos[i][j]=pos[i-1][j];//pos数组用来保存 计算出线性基第j个基的元素的位置
}

继承之后我们就可以求解当前区间的线性基了。

在求解时，我们需要用贪心的策略对线性基进行更新：

k=i;
for(int j=30;j>=0;j--){
    if(x>>j){
        if(!f[i][j]){
            f[i][j]=x;
            pos[i][j]=k;
            break;
        }
        else{
            //这一步是贪心策略，将计算出基的元素尽量的靠右
            //由线性基的性质可知，在替换掉当前元素后，线性基的性质和表示范围不会发生改变。
            if(k>pos[i][j]){
                swap(k,pos);
                swap(x,f[i][j]);
            }
            x^=f[i][j];
        }
    }
}

查询区间最大值

假设需要计算的区间为 [l,r] （已经过转换），那么我们接下来就要根据利用线性基求子集最大值的方法来进行求解了。

对于 f[i][j] ,我们可以知道这个基的有效范围为 [1,pos[i][j]] ,当 l>pos[i][j]时 这个基就已经没有了计算的意义。

所以使用 S=\lbrace f[r][j]~| l \leq pos[r][j] \rbrace 就能够用来表示区间 [l,r] 的所有子集异或和：

ans=0;
for(int j=30;j>=0;j--){
    if((ans^f[r][j])>ans && pos[r][j]>=l)
        ans^=f[r][j];
}

这样就能够简便的计算出区间 [l,r] 子集的异或和最大值。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int t,n,m,l,r,op,res;
int a[maxn];
int f[maxn][32],pos[maxn][32];
void add(int i,int x){
    int k=i;
    for(int j=30;j>=0;j--){
        f[i][j]=f[i-1][j];
        pos[i][j]=pos[i-1][j];
    }
    for(int j=30;j>=0;j--){
        if(x>>j){
            if(!f[i][j]){
                f[i][j]=x;
                pos[i][j]=k;
                break;
            }
            else{
                if(k>pos[i][j]){
                    swap(k,pos[i][j]);
                    swap(x,f[i][j]);
                }
                x^=f[i][j];
            }
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        res=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            add(i,a[i]);
        }
        while(m--){
            scanf("%d",&op);
            if(op){
                scanf("%d",&a[++n]);
                a[n]=a[n]^res;
                add(n,a[n]);
            }
            else{
                scanf("%d %d",&l,&r);
                l=(l^res)%n+1;r=(r^res)%n+1;
                if(l>r) swap(l,r);
                res=0;
                for(int j=30;j>=0;j--){
                    if((res^f[r][j])>res && pos[r][j]>=l)
                        res^=f[r][j];
                }
                printf("%d\n",res);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=30;j>=0;j--){
                f[i][j]=pos[i][j]=0;
            }
        }
    }
    return 0;
}