「BZOJ 3533」向量集-线段树 + 凸包 + 三分

维护一个向量集合,在线支持:

  1. 加入向量 $(x, y)$;
  2. 询问 $[l, r]$ 中的向量与向量 $(x, y)$ 的点积最大值。

链接

BZOJ 3533

题解

显然询问点积最大值就是维护上下两个凸壳,然后在对应的凸壳上三分就好了。

对于区间询问,我们考虑用线段树维护,注意到线段树修改时要进行 maintain 操作,而直接合并两个凸包是 $O(size)$ 的,所以不能每次插入都 maintain

注意到题目中每次都是在末尾加入一个向量,所以我们可以在当前区间全部插入完后进行 maintain,即插入的节点是当前节点的右儿子时。

由于合并的时候要按 $x$ 排序,直接 std::sort 插入的复杂度会多一个 $\log$,由于儿子维护凸壳是有序的,直接调用 std::merge 就好了(当然你可以手写归并)。

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

普通线段树好慢,ZKW 快好几倍…

代码

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
/**
* 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 3533」向量集 27-02-2018
* 线段树 + 凸包 + 三分
* @author xehoth
*/
#include <algorithm>
#include <cctype>
#include <climits>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <vector>
inline void *operator new(size_t size) {
static const int POOL_SIZE = 1024 * 1024 * 70;
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() : s(), t(), oh(obuf) {}
~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
inline char read() {
return (s == t) && (t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin)),
s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
iosig |= c == '-';
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig && (x = -x);
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(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;
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
inline Point operator+(const Point &p) const {
return Point(x + p.x, y + p.y);
}
inline Point operator-(const Point &p) const {
return Point(x - p.x, y - p.y);
}
inline long long operator*(const Point &p) const {
return (long long)x * p.y - (long long)y * p.x;
}
inline bool operator<(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
};
inline long long dot(const Point &a, const Point &b) {
return (long long)a.x * b.x + (long long)a.y * b.y;
}
const int MAXM = 1048574 + 3;
typedef std::vector<Point> Vector;
struct Node {
Vector up, down;
bool f;
} d[MAXM];
int M, n, online, cnt;
long long lastans;
inline int decode(int x) { return x ^ (lastans & 0x7fffffff); }
inline bool fUp(long long x) { return x >= 0; }
inline bool fDown(long long x) { return x <= 0; }
template <bool (*f)(long long)>
inline void update(Vector &c, Vector &l, Vector &r) {
c.resize(l.size() + r.size());
std::merge(l.begin(), l.end(), r.begin(), r.end(), c.begin());
int top = 0, n = c.size();
for (int i = 0; i < n; i++) {
while (top > 1 && f((c[top - 1] - c[top - 2]) * (c[i] - c[top - 2])))
top--;
c[top++] = c[i];
}
c.resize(top);
}
inline void maintain(int k) {
Node &lc = d[k << 1], &rc = d[k << 1 | 1];
update<fUp>(d[k].up, lc.up, rc.up);
update<fDown>(d[k].down, lc.down, rc.down);
}
inline long long get(const Vector &c, const Point &p) {
int l = 0, r = c.size() - 1;
for (int lMid, rMid; r - l > 2;) {
lMid = l + (r - l) / 3;
rMid = r - (r - l) / 3;
if (dot(c[lMid], p) > dot(c[rMid], p))
r = rMid;
else
l = lMid;
}
long long ans = LLONG_MIN;
for (; l <= r; l++) ans = std::max(ans, dot(c[l], p));
return ans;
}
inline long long query(int k, const Point &p) {
return p.y > 0 ? get(d[k].up, p) : get(d[k].down, p);
}
inline long long query(int s, int t, const Point &p) {
long long ret = LLONG_MIN;
for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
if (~s & 1) ret = std::max(ret, query(s ^ 1, p));
if (t & 1) ret = std::max(ret, query(t ^ 1, p));
}
return ret;
}
int main() {
// freopen("sample/1.in", "r", stdin);
char cmd;
io >> n >> cmd;
online = (cmd != 'E');
for (M = 1; M < n + 2;) M <<= 1;
Point pts;
for (int i = 1, l, r, p; i <= n; i++) {
io >> cmd;
io >> pts.x >> pts.y;
if (online) {
pts.x = decode(pts.x);
pts.y = decode(pts.y);
}
switch (cmd) {
case 'A': {
d[p = ++cnt + M].f = true;
d[p].up.push_back(pts);
d[p].down.push_back(pts);
for (p >>= 1; p && d[p << 1 | 1].f; p >>= 1) {
maintain(p);
d[p].f = true;
d[p << 1 | 1].f = false;
}
break;
}
case 'Q': {
io >> l >> r;
if (online) {
l = decode(l);
r = decode(r);
}
lastans = query(l, r, pts);
io << lastans << '\n';
break;
}
}
}
}
分享到