无效位置(离线+线性基合并)

描述

传送门:Wannafly挑战赛14 - Problem E

给一个$1-base$数组$\lbrace a \rbrace$,有$N$次操作,每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前,所有不包含无效位置的区间的权值的最大值。

输入描述

第一行读入一个正整数($1 ≤ n ≤ 10^5$)

第二行读入$n$个正整数,第$i$个表示$a[i]$($0≤ a[i] ≤ 10^9$)

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

输出描述

输出$n$行答案

样例输入

1
2
3
10
169 816 709 896 58 490 97 254 99 796
4 2 3 10 5 6 1 8 9 7

样例输出

1
2
3
4
5
6
7
8
9
10
1023
994
994
994
490
490
254
254
99
97

思路

  • 异或最大,想到线性基。但是维护线性基没法做删除操作。
  • 考虑整个操作的逆过程,就是将若干个线性基合并起来。这点在并查集的帮助下可以很轻松地完成。
  • 然后……就没有然后了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 1 << 17;
struct L_B
{
int d[31];
L_B() { memset(d, 0, sizeof(d)); }
bool insert(int val)
{
for (int i = 30; ~i; i--)
if (val >> i & 1)
{
if (!d[i])
{
d[i] = val;
break;
}
val ^= d[i];
}
return val > 0;
}
int query_max()
{
int ret = 0;
for (int i = 30; ~i; i--)
if ((ret ^ d[i]) > ret) ret ^= d[i];
return ret;
}
} base[N];

L_B merge(const L_B& a, const L_B& b)
{
L_B ret = a;
for (int i = 30; ~i; i--)
if (b.d[i]) ret.insert(b.d[i]);
return ret;
}

int fa[N], ans;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return;
fa[y] = x;
base[x] = merge(base[x], base[y]);
ans = max(ans, base[x].query_max());
}

bool ok[N];
int a[N], b[N],ret[N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++) scanf("%d", b + i);
for (int i = n; i; i--)
{
ok[b[i]] = 1;
base[b[i]].insert(a[b[i]]);
ans = max(ans, base[b[i]].query_max());
if (ok[b[i] - 1]) unite(b[i], b[i] - 1);
if (ok[b[i] + 1]) unite(b[i], b[i] + 1);
ret[i] = ans;
}
for (int i = 1; i <= n; i++) printf("%lld\n", ret[i]);
return 0;
}
捐助作者
0%