CF1100F Ivan and Burgers

题目地址：CF1100F Ivan and Burgers

一道有难度的线性基题，看了题解才会做

预处理两个数组：

\(p_{r,i}\) 表示满足下列条件的最大的 \(l\) ：线性基第 \(i\) 位有值且 \(l\leq r\)

\(b_{r,i}\) 表示此时第 \(i\) 位的线性基

对于每个询问，从高往低位取

当然这个方法也能离线做

时间复杂度为 \(O(nlog\ n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 500006;
int n, q, b[N][21], p[N][21];

inline void get(int x, int k, int r) {
    for (int i = 20; i >= 0; i--)
        if ((x >> i) & 1) {
            if (!b[r][i]) {
                b[r][i] = x;
                p[r][i] = k;
                return;
            }
            if (p[r][i] < k) {
                swap(p[r][i], k);
                swap(x, b[r][i]);
            }
            x ^= b[r][i];
        }
}

inline int work(int l, int r) {
    int ans = 0;
    for (int i = 20; i >= 0; i--)
        if (p[r][i] >= l) ans = max(ans, ans ^ b[r][i]);
    return ans;
}

int main() {
    cin >> n;
    for (int r = 1; r <= n; r++) {
        int x;
        scanf("%d", &x);
        memcpy(b[r], b[r-1], sizeof(b[r]));
        memcpy(p[r], p[r-1], sizeof(p[r]));
        get(x, r, r);
    }
    cin >> q;
    while (q--) {
        int l, r;
        scanf("%d %d", &l ,&r);
        printf("%d\n", work(l, r));
    }
    return 0;
}

巴特西

CF1100F Ivan and Burgers

题目地址：CF1100F Ivan and Burgers

一道有难度的线性基题，看了题解才会做

预处理两个数组：

\(p_{r,i}\) 表示满足下列条件的最大的 \(l\) ：线性基第 \(i\) 位有值且 \(l\leq r\)

\(b_{r,i}\) 表示此时第 \(i\) 位的线性基

对于每个询问，从高往低位取

当然这个方法也能离线做

时间复杂度为 \(O(nlog\ n)\)

代码：

最新文章

热门文章