「BZOJ 4137」火星商店问题-线段树分治 + 可持久化 Trie

有 $n$ 个商店,每个商店中各有一个特殊物品,特殊物品会一直供应;按照时间顺序(令时间为 $\mathrm{day}$)有 $m$ 个下列事件:

  1. 第 $s$ 个商店在当日新进一种价值为 $v$ 的商品,$\mathrm{day}++$;
  2. 询问第 $L$ 到第 $R$ 的商店购买 $d$ 天内的商品价值 $\mathrm{xor} \ x$ 的最大值。

链接

BZOJ 4137

题解

显然可以树套树,对商店 $1 \sim n$ 建线段树,然后内层套 Trie 树,但是空间限制只有 256 MB,不太可行。

考虑线段树分治,对于时间建立线段树,线段树上维护当前时间段需要的修改和询问,具体实现就是用 std::vector 存下当前节点的修改和询问。

预处理出询问可以购买的商品的时间区间,将其插入线段树。

区间异或最大值显然要用可持久化 Trie,而可持久化 Trie 插入时要按照顺序插入,所以我们先将修改按照商店排序,然后加入线段树。

然后从线段树根节点开始分治,先处理当前节点的修改,然后回答询问即可。

时间复杂度 $O(n \log ^ 2 n)$,空间复杂度 $O(n \log 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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
/**
* 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 4137」火星商店问题 28-02-2018
* 线段树分治 + 可持久化 Trie
* @author xehoth
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>
#include <vector>
inline void *operator new(size_t size) {
static const int POOL_SIZE = 1024 * 1024 * 20;
static char pool[POOL_SIZE], *s = pool;
char *t = s;
s += size;
return t;
}
inline void operator delete(void *) {}
inline void operator delete(void *, size_t) {}
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 MAXN = 100000 + 9;
const int MAX_LOG = 17;
const int MAXM = MAXN * (MAX_LOG + 1);
struct Node *null;
char *cur;
struct Node {
static const int NODE_SIZE;
Node *c[2];
int cnt;
inline void *operator new(size_t) { return cur += NODE_SIZE; }
Node() : cnt() { c[0] = c[1] = null; }
};
const int Node::NODE_SIZE = sizeof(Node);
char pool[MAXM * Node::NODE_SIZE];
void insert(Node *&p, Node *pre, int v, int dep = MAX_LOG - 1) {
p = new Node(*pre);
p->cnt++;
if (dep < 0) return;
int d = v >> dep & 1;
insert(p->c[d], pre->c[d], v, dep - 1);
}
int query(Node *l, Node *r, int v, int dep = MAX_LOG - 1) {
if (dep < 0) return 0;
int d = v >> dep & 1;
if (r->c[d ^ 1]->cnt - l->c[d ^ 1]->cnt > 0)
return (1 << dep) | query(l->c[d ^ 1], r->c[d ^ 1], v, dep - 1);
return query(l->c[d], r->c[d], v, dep - 1);
}
Node *root[MAXN];
inline int query(int l, int r, int v) {
return l - 1 > r ? 0 : query(root[l - 1], root[r], v);
}
struct Modify {
int t, s, v;
inline bool operator<(const Modify &p) const { return s < p.s; }
} mdf[MAXN];
struct Query {
int L, R, l, r, x, *ans;
} que[MAXN];
struct SegmentTree {
std::vector<Modify *> m;
std::vector<Query *> q;
} d[262145];
void insert(int k, int l, int r, int pos, Modify *m) {
d[k].m.push_back(m);
if (l == r) return;
int mid = (l + r) >> 1;
pos <= mid ? insert(k << 1, l, mid, pos, m)
: insert(k << 1 | 1, mid + 1, r, pos, m);
}
void insert(int k, int l, int r, int s, int t, Query *m) {
if (s <= l && t >= r) {
d[k].q.push_back(m);
return;
}
int mid = (l + r) >> 1;
if (s <= mid) insert(k << 1, l, mid, s, t, m);
if (t > mid) insert(k << 1 | 1, mid + 1, r, s, t, m);
}
inline bool cmpModify(const Modify *a, const Modify *b) { return a->s < b->s; }
inline bool equalModify(const Modify *a, const Modify *b) {
return a->s == b->s;
}
inline void solveNode(SegmentTree &p) {
cur = pool;
root[0] = null;
int rtn = 0;
for (int i = 0; i < (int)p.m.size(); i++) {
rtn++;
insert(root[rtn], root[rtn - 1], p.m[i]->v);
while (i + 1 < (int)p.m.size() && p.m[i]->s == p.m[i + 1]->s)
insert(root[rtn], root[rtn], p.m[++i]->v);
}
p.m.erase(std::unique(p.m.begin(), p.m.end(), equalModify), p.m.end());
Modify tmp;
for (int i = 0, l, r; i < (int)p.q.size(); i++) {
tmp.s = p.q[i]->L;
l = std::lower_bound(p.m.begin(), p.m.end(), &tmp, cmpModify) -
p.m.begin() + 1;
tmp.s = p.q[i]->R;
r = std::upper_bound(p.m.begin(), p.m.end(), &tmp, cmpModify) -
p.m.begin();
*p.q[i]->ans = std::max(*p.q[i]->ans, query(l, r, p.q[i]->x));
}
}
void solve(int k, int l, int r) {
solveNode(d[k]);
if (l == r) return;
int mid = (l + r) >> 1;
solve(k << 1, l, mid);
solve(k << 1 | 1, mid + 1, r);
}
int day, n, m, ans[MAXN], mt, qt;
int main() {
// freopen("sample/1.in", "r", stdin);
cur = pool;
null = (Node *)pool;
null->c[0] = null->c[1] = null;
null->cnt = 0;
io >> n >> m;
for (int i = 0; i <= n; i++) root[i] = null;
for (int i = 1, x; i <= n; i++) {
io >> x;
insert(root[i], root[i - 1], x);
}
for (int i = 1, cmd, qd; i <= m; i++) {
io >> cmd;
switch (cmd) {
case 0: {
mt++;
mdf[mt].t = ++day;
io >> mdf[mt].s >> mdf[mt].v;
break;
}
case 1: {
qt++;
io >> que[qt].L >> que[qt].R >> que[qt].x >> qd;
que[qt].l = std::max(day - qd, 0) + 1;
que[qt].r = day;
que[qt].ans = ans + qt;
ans[qt] = query(que[qt].L, que[qt].R, que[qt].x);
break;
}
}
}
std::sort(mdf + 1, mdf + mt + 1);
for (int i = 1; i <= mt; i++) insert(1, 1, day, mdf[i].t, mdf + i);
for (int i = 1; i <= qt; i++)
if (que[i].l <= que[i].r)
insert(1, 1, day, que[i].l, que[i].r, que + i);
solve(1, 1, day);
for (int i = 1; i <= qt; i++) io << ans[i] << '\n';
return 0;
}
分享到