bzoj 4311 向量

题目描述

https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-4311

简要题意:现在有 $n$ 次操作,操作分三种,第一种操作是向集合中插入一个向量 $(x,y)$,第二种操作是删除集合中的一个向量,第三种操作是求集合中的所有向量与给定向量 $(x,y)$ 的点积的最大值

$n\le 2\times 10^5,1\le x,y\le 10^6$

Solution

对于插入和删除,我们直接上线段树分治即可

我们考虑化一下式子,令给定的向量为 $(x_0,y_0)$,那么我们有 $x_0x+y_0y=ans$,$y=-\frac{x_0}{y_0}x+\frac{ans}{y_0}$,我们将其看成直线,容易得到我们需要最大化截距,那么我们直接维护上凸壳,查询时三分即可

时间复杂度 $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
#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 200010
#define ll long long
using namespace std;

int n;

struct point {
int x, y;
} Q[maxn]; int q;

struct node {
point p;
int l, r;

friend bool operator < (const node &u, const node &v) {
if (u.p.x == v.p.x) return u.p.y < v.p.y;
return u.p.x < v.p.x;
}
} a[maxn]; int cnt;

#define lc i << 1
#define rc i << 1 | 1
vector<point> T[maxn * 4];
void update(int i, int l, int r, int L, int R, point v) {
if (l > R || r < L) return ;
if (L <= l && r <= R) {
int k = T[i].size() - 1;
while (k > 0 && 1ll * (v.y - T[i][k - 1].y) * (T[i][k].x - T[i][k - 1].x) >=
1ll * (T[i][k].y - T[i][k - 1].y) * (v.x - T[i][k - 1].x)) --k, T[i].pop_back();
return T[i].push_back(v);
} int m = l + r >> 1;
update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}

ll query(int i, int l, int r, int k, point v) {
int L = 0, R = T[i].size() - 1, m1, m2; ll s1, s2, ans = 0;
while (L <= R) {
m1 = L + (R - L) / 3;
m2 = R - (R - L) / 3;
s1 = 1ll * v.x * T[i][m1].x + 1ll * v.y * T[i][m1].y;
s2 = 1ll * v.x * T[i][m2].x + 1ll * v.y * T[i][m2].y;
if (s1 > s2) R = m2 - 1, ans = max(ans, s1);
else L = m1 + 1, ans = max(ans, s2);
}
if (l == r) return ans; int m = l + r >> 1;
if (k <= m) return max(ans, query(lc, l, m, k, v));
else return max(ans, query(rc, m + 1, r, k, v));
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);

cin >> n;
for (int i = 1; i <= n; ++i) {
int opt, x, y; cin >> opt;
if (opt == 1) {
cin >> x >> y;
a[++cnt] = { { x, y }, i, 0 };
}
else if (opt == 2) cin >> x, a[x].r = i - 1;
else {
cin >> x >> y;
Q[i] = { x, y };
}
} sort(a + 1, a + cnt + 1);
for (int i = 1; i <= n; ++i) if (!a[i].r) a[i].r = n;
for (int i = 1; i <= n; ++i) update(1, 1, n, a[i].l, a[i].r, a[i].p);
for (int i = 1; i <= n; ++i) if (Q[i].x) cout << query(1, 1, n, i, Q[i]) << "\n";
return 0;
}