「BZOJ 4184」shallot-线段树分治 + 线性基

对于时刻 $1 \sim n$,要求支持:

  1. 加入一个数 $a$;
  2. 删除一个已加入的数 $a$。

求每个时刻所有数的最大异或和。

链接

BZOJ 4184

题解

加入数,求最大异或和,显然是线性基,但是线性基不支持删除,此题允许离线,所以我们可以考虑用线段树分治来维护。

以时间建立线段树,每个节点维护一个线性基表示当前时间段的线性基。

预处理出每个数出现时间的区间,然后将其加入线段树。

由于要询问每个时刻的最大异或和,如果每次单点询问,就会合并 $\log$ 次线性基,这样复杂度会多一个 $\log$,所以我们可以把父节点的线性基一层一层下传到儿子节点,最后在叶子节点处询问即可。

时间复杂度 $O(n \log ^ 2 n)$。

注意空间…

代码

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/**
* Copyright (c) 2016-2018, xehoth
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* 「BZOJ 4184」shallot 28-02-2018
* 线段树分治 + 线性基
* @author xehoth
*/
#include <bits/stdc++.h>
struct InputOutputStream {
enum { SIZE = 1 << 18 | 1 };
char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
InputOutputStream() : s(), t(), oh(obuf) {}
inline char read() {
return (s == t) && (t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin)),
s == t ? -1 : *s++;
}
template <typename T>
inline InputOutputStream &operator>>(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return *this;
iosig |= c == '-';
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig && (x = -x);
return *this;
}
inline void print(char c) {
(oh == obuf + SIZE) && (fwrite(obuf, 1, SIZE, stdout), oh = obuf);
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[21], cnt;
if (x != 0) {
(x < 0) && (print('-'), x = -x);
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
} else {
print('0');
}
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
} io;
const int MAX_LOG = 31;
const int MAXN = 500000;
const int MAXM = 1048576 + 1;
struct LinearBasis {
unsigned int a[MAX_LOG];
inline void insert(unsigned int x) {
for (int i; x;) {
if (a[i = MAX_LOG - __builtin_clz(x)]) {
x ^= a[i];
} else {
a[i] = x;
break;
}
}
}
inline unsigned int query() {
unsigned int ret = 0;
for (int i = MAX_LOG - 1; i >= 0; i--)
if ((ret ^ a[i]) > ret) ret ^= a[i];
return ret;
}
inline unsigned int &operator[](int i) { return a[i]; }
inline const unsigned int &operator[](int i) const { return a[i]; }
} d[MAXM];
int M, n;
std::map<int, int> map;
inline void modify(int s, int t, int x) {
for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
if (~s & 1) d[s ^ 1].insert(x);
if (t & 1) d[t ^ 1].insert(x);
}
}
int main() {
// freopen("sample/1.in", "r", stdin);
io >> n;
for (M = 1; M < n + 2;) M <<= 1;
for (int i = 1, x; i <= n; i++) {
io >> x;
if (x > 0) {
map[x] = i;
} else {
std::map<int, int>::iterator it = map.find(-x);
modify(it->second, i - 1, -x);
map.erase(it);
}
}
for (std::map<int, int>::iterator it = map.begin(); it != map.end(); ++it)
modify(it->second, n, it->first);
for (int i = 1; i < M; i++) {
for (int j = 0; j < MAX_LOG; j++) {
d[i << 1].insert(d[i][j]);
d[i << 1 | 1].insert(d[i][j]);
}
}
for (int i = 1; i <= n; i++) io << d[i + M].query() << '\n';
return 0;
}
分享到