2019 Multi-University Training Contest 1 1002 Operation 线性基
线性基   发布于 2019-07-27   397人围观  0条评论
线性基   发表于 2019-07-27   397人围观  0条评论

题目大意

给出一个序列,有两种操作你需要完成:

0操作:询问l-----r区间内所有数中部分数通过异或运算所组成的所有数中的最大值。

1操作:在序列尾部插入值x。

注意题目强制在线。

题解

此题是个强制在线的题目,不能使用离线算法(如莫队、CDQ分治)完成。

从0操作我们可以看出来此题很明显是一个线性基的题目(线性基主要用来解决序列中取出若干数使得这些数的异或值最大的问题,当然线性基也可以放入图论问题中)

如果没学过线性基的建议先自学线性基,本篇只是线性基的应用。可能之后我会写线性基的博客吧。

线性基是可以使用一些数据结构维护的,很多人比赛的时候看到这道题要进行区间操作就直接上线段树平衡树来维护线性基了。但是由于这道题的数据范围过大,数据结构会有logn的一个复杂度导致超时。

这道题的正确的思路是贪心地维护以某个位置为结尾的所有数的线性基。

对于每一个线性基,我们尽量把出现时间较为靠后的数的二进制向量放在高位上,然后原来的线性基中各位置上的二进制向量不断下放。如此地贪心地维护以每个位置为结尾的线性基。

在求最大值的时候,首先找到区间右端点对应结尾的线性基,然后从高位向低位开始扫,如果当前扫到的线性基的位置为第j位,且第j位上的二进制向量出现的比查询区间左端点l要晚,那我们就要考虑这个二进制向量对答案的影响,如果异或此二进制向量能够使得答案变大,那我们就异或上这个二进制向量。否则就不需要考虑。

这样我们得出的线性基就有一个性质:对于每个线性基的每一位,与它异或过的线性基更高位置上的数字肯定都出现在它右侧 (否 则它就会被插入在那个位置了),因此做法的正确性显然。

最终复杂度位O(31*n)。(注意此题的强制在线的操作)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn =  5e5+5;
int n,m;
int T;
int opt,l,r,x;
int f[maxn<<1][31],id[maxn<<1][31];
int last;
void add(int pos,int x){
    int k = pos;
    for(int j = 30;j >= 0;--j)
        f[pos][j] = f[pos-1][j],id[pos][j] = id[pos-1][j];
    for(int j = 30;j >= 0;--j){
        if(x & (1<<j)){
            if(!f[pos][j]){
                f[pos][j] = x;
                id[pos][j] = k;
                break;
            }
            else{
                if(k > id[pos][j]){
                    swap(k,id[pos][j]);
                    swap(x,f[pos][j]);
                }
                x ^= f[pos][j];
            }
        }
    }
    return;
}
int main(){
    T = get_num();
    while(T--){
        n = get_num();
        m = get_num();
        last = 0;
        for(int i = 1;i <= n+m;++i)
            for(int j = 0;j <= 30;++j)f[i][j] = 0;
        for(int i = 1;i <= n;++i){
            x = get_num();
            add(i,x);
        }
        while(m--){
            opt = get_num();
            if(opt == 1){
                x = get_num();
                x ^= last;
                add(++n,x);
            }
            else if(opt == 0){
                l = get_num();
                r = get_num();
                l = (l ^ last) % n + 1;
                r = (r ^ last) % n + 1;
                last = 0;
                if(l > r)swap(l,r);
                for(int j = 30;j >= 0;--j){
                    if(id[r][j] >= l && (last ^ f[r][j]) > last)
                        last ^= f[r][j];
                }
                printf("%d\n",last);
            }
        }
    }
    return 0;
}


上一篇: 2019 Multi-University Training Contest 3 Game 经典NIM博弈SG函数 + 带修改莫队

下一篇: 2019 Multi-University Training Contest 1 1005 Path 最小割+最短路

立即登录,发表评论
没有帐号?立即注册
0 条评论