牛客 无效位置（并查集 + 线性基合并）

链接：https://ac.nowcoder.com/acm/problem/15710
来源：牛客网

题目描述
给一个1-base数组{a}，有N次操作，每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前，所有不包含无效位置的区间的权值的最大值。

输入描述:
第一行读入一个正整数(1 <= n <= 105)

第二行读入n个正整数，第i个表示a[i](0<= a[i] <= 109)

第三行读入n个正整数，第i个表示x[i]即第i次操作的位置，保证x[i]互不相同。

输出描述:
输出n行答案
示例1
输入
复制
10
169 816 709 896 58 490 97 254 99 796
4 2 3 10 5 6 1 8 9 7
输出
复制
1023
994
994
994
490
490
254
254
99
97

#include <bits/stdc++.h>
using namespace std;
//线性基模板
typedef long long ll;
struct Lbase{
    ll p[64], q[64], tot;
    bool zero;
    Lbase() {
        memset(p, 0, sizeof(p)); tot = 0; zero = false;
    }
    //插入线性基（false插入失败） （true插入成功）
    bool insert(ll x) {
        for (int i = 62; i >= 0; i--) {
            if ((x >> i) & 1) {
                if (!p[i]) {p[i] = x; return true;}
                x ^= p[i];
            }
        }
        //是否能异或出0
        zero = true;
        return false;
    }
    //判断x是否能够通过线性基得到
    bool find(ll x) {
        if (x == 0 && zero) return true;
        for (int i = 62; i >= 0; i--) if ((x >> i) & 1) x ^= p[i];
        return (x == 0);
    }
    //两个线性基合并
    Lbase meger(Lbase a, Lbase b) {
        Lbase c;
        for (int i = 62; i >= 0; i--) {
            if (a.p[i]) c.insert(a.p[i]);
            if (b.p[i]) c.insert(b.p[i]);
        }
        return c;
    }
    //返回线性基中的最大值
    ll findMax(ll x) {
        ll ans = x;
        for (int i = 62; i >= 0; i--) {
            if (p[i]) ans = max(ans, ans ^ p[i]);
        }
        return ans;
    }
    //返回线性基中的最小值
    ll findMin(ll x) {
        ll ans = x;
        for (int i = 62; i >= 0; i--) {
            if (p[i]) ans = min(ans, ans ^ p[i]);
        }
        return ans;
    }
    //重新构建线性基
    void reBuild() {
        for (int i = 62; i >= 0; i--) q[i] = p[i];
        for (int i = 62; i >= 0; i--) {
            if (q[i] == 0) continue;
            for (int j = i - 1; j >= 0; j--) {
                if (q[j] == 0) continue;
                if ((q[i] & (1LL << j))) q[i] ^= q[j];
            }
        }
        for (int i = 0; i <= 62; i++) {
            if (q[i]) q[tot++] = q[i];
        }
    }
    //查找第K大异或值
    ll findKth(ll k) {
        if (zero) k--;
        ll ans = 0;
        if (k == 0) return 0;
        if (k >= (1LL << tot)) return -1;
        for (int i = 62; i >= 0; i--) {
            if (k & (1LL<<i)) ans ^= q[i];
        }
        return ans;

    }
    //返回线性基异或数量
    ll getTot() {
        return tot ? (((1LL << tot) - 1) + zero) : 0;
    }
};
const int maxn = 1e5 + 5;
Lbase lbase[maxn];
int fa[maxn], b[maxn];
ll ans[maxn], a[maxn];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    int n, pos, x;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    for (int i = n; i >= 1; i--) {
        fa[b[i]] = b[i];
        lbase[b[i]].insert(a[b[i]]);
        if (fa[b[i] + 1]) {
            int u = find(fa[b[i]]);
            int v = find(fa[b[i] + 1]);
            fa[v] = u;
            lbase[u] = lbase[u].meger(lbase[u], lbase[v]);
        }
        if (fa[b[i] - 1]) {
            int u = find(fa[b[i]]);
            int v = find(fa[b[i] - 1]);
            fa[v] = u;
            lbase[u] = lbase[u].meger(lbase[u], lbase[v]);
        }
        ans[i] = max(1LL * ans[i + 1], lbase[b[i]].findMax(0));
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}