Operation HDU

Operation (HDU - 6579)

番外：

初学线性基，推荐一篇线性基学习笔记。

线性基就是一个两两元素异或没有冗余的元素集合。

我们在集合内每一位记录一个贡献当前位的数字，就可以查询区间异或极值。

题意：

给一个初始序列，要求支持两种操作：

• 查询一个区间内的元素异或最大值。
• 向序列尾部添加一个元素。

题解：

我们考虑做一个前缀线性基和，然后插入元素的同时记录坐标，来保证让贡献高位的元素尽量靠右。这样可以保证在每个线性基和里查询区间的时候，查询到的数尽量大（贡献的位置尽量高）。查询的时候只查询坐标大于等于L的就可以了。

#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 5;
typedef pair<int, int> Pair;

struct LinearBasis{
    #define N 30
    Pair a[N+1];

    void init() {
        memset(a, 0, sizeof(a));
    }

    bool insert(int val, int pos) {
        for (int i = N; i >= 0; i--) if (val & (1ll << i)) {
            if (a[i].first == 0) {
                a[i].first = val;
                a[i].second = pos;
                break;
            }
            else if (a[i].second < pos) {
                swap(val, a[i].first);
                swap(pos, a[i].second);
            }
            val ^= a[i].first;
        }
        return val > 0;
    }

    int query_Max(int l) {
        int res = 0;
        for (int i = N; i >= 0; i--)
            if ((res^a[i].first) > res && a[i].second >= l)
                res ^= a[i].first;
        return res;
    }
}LB[maxn];

int T, n, m;
LL x;

int main() {

    //fopi;

    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca++) {
        LB[0].init();

        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &x);
            LB[i] = LB[i-1];
            LB[i].insert(x, i);
        }

        int ans = 0;
        for (int i = 1; i <= m; i++) {
            int op, x, y;
            scanf("%d%d", &op, &x);
            if (op == 0) {
                scanf("%d", &y);
                x = (x^ans) % n + 1, y = (y^ans) % n + 1;
                if (x > y) swap(x, y);
                printf("%d
", ans = LB[y].query_Max(x));
            }
            else {
                ++n;
                LB[n] = LB[n-1];
                LB[n].insert(x^ans, n);
            }
        }
    }
}