HDU6579 2019HDU多校训练赛第一场1002 （线性基）

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6579

题意：

两种操作

1.在序列末尾添加一个数

2.查询区间异或最大值

强制在线

题解：

暴力的做法可以用数据结构维护区间线性基，但肯定过不了。

贪心地维护序列的前缀线性基 (上三角形态)，对于每个线性基，将出现位置靠右的数

字尽可能地放在高位，也就是说在插入新数字的时候，要同时记录对应位置上数字的出现位

置，并且在找到可以插入的位置的时候，如果新数字比位置上原来的数字更靠右，就将该位

置上原来的数字向低位推。

在求最大值的时候，从高位向低位遍历，如果该位上的数字出现在询问中区间左端点的

右侧且可以使答案变大，就异或到答案里。

对于线性基的每一位，与它异或过的线性基更高位置上的数字肯定都出现在它右侧 (否

则它就会被插入在那个位置了)，因此做法的正确性显然。

代码：

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 1e6 + 5;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + 7;

LL quick_pow(LL x, LL y) {

    LL ans = 1;

    while(y) {

        if(y & 1) {

            ans = ans * x % mod;

        } x = x * x % mod;

        y >>= 1;

    } return ans;

}

int f[maxn][32];

int pos[maxn][32];

void add(int x, int i) {

    int k = i;

    int tmp;

    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]) {

                    tmp = k, k = pos[i][j], pos[i][j] = tmp;

                    tmp = x, x = f[i][j], f[i][j] = tmp;

                }

                x ^= f[i][j];

            }

        }

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    int T;

    scanf("%d", &T);

    while(T--) {

        memset(pos, 0, sizeof(pos));

        memset(f, 0, sizeof(f));

        int n, m;

        scanf("%d%d", &n, &m);

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

            scanf("%d", &x);

            add(x, i);

        }

        int lastans = 0;

        while(m--) {

            int op;

            int l, r, x;

            scanf("%d", &op);

            if(op == 0) {

                scanf("%d%d", &l, &r);

                // debug2(l, r);

                l = (l ^ lastans) % n + 1;

                r = (r ^ lastans) % n + 1;

                if(l > r) swap(l, r);

                int ans = 0;

                for(int j = 30; j >= 0; --j) {

                    if((ans ^ f[r][j]) > ans && pos[r][j] >= l) {

                        ans ^= f[r][j];

                    }

                }

                printf("%d\n", ans);

                lastans = ans;

            } else {

                scanf("%d", &x);

                x^=lastans;

                n++;

                add(x, n);

            }

        }

    }

    return 0;

}