链接: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; }