BZOJ4311 向量 <线段树分治+凸包>

Posted on Symbols count in article: 1k Reading time ≈ 4 mins.

Problem

向量

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

你要维护一个向量集合，支持以下操作：

  1. 插入一个向量(x,y)(x,y)
  2. 删除插入的第ii个向量
  3. 查询当前集合与(x,y)(x,y)点积的最大值是多少，如果当前是空集输出0

Input

第一行输入一个整数nn，表示操作个数
接下来nn行，每行先是一个整数tt表示类型，如果t=1t=1，输入向量(x,y)(x,y)；如果t=2t=2，输入idid表示删除第idid个向量；否则输入(x,y)(x,y)，查询与向量(x,y)(x,y)点积最大值是多少
保证一个向量只会被删除一次，不会删没有插入过的向量

Output

对于每条t=3t=3的询问，输出一个答案

Sample Input

1
2
3
4
5
6
5
1 3 3
1 1 4
3 3 3
2 1
3 3 3

Sample Output

1
2
18
15

HINT

n≤2×105n\le2\times10^5，1≤x,y≤1061\le x,y\le10^6。

标签：线段树分治 凸包

Solution

不考虑删除操作，由于点积最大的点一定在上凸壳上，可以用线段树维护凸包，支持插入一个点，三分询问一个点与凸壳上的点的最大点积。
然而有删除操作，发现每个点只在一个时间区间中存在，于是可以对时间进行线段树分治，将每个点存在区间分为log⁡m\log{m}个（mm为询问总数），这样对于一个询问，可能成为其答案的点一定存在于其到根的路径上。
对于每一个时间段结点，求出这个结点上所有点的上凸壳，并回答在这个点所代表区间内的所有询问即可。由于可以先处理两个子区间，再处理这个区间，所以顺便对询问归并排序一下也是可行的，可以避免凸包上三分。由于一个点被拆到log⁡m\log{m}个区间中，且每次只会加入一次栈，而询问则是进行归并排序并在每个凸壳上O(1)O(1)打擂，因此总时间复杂度为O(nlog⁡m+mlog⁡m)O(n\log{m}+m\log{m})。

Code

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 <bits/stdc++.h>
#define x first
#define y second
#define MAX_N 200000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
typedef pair<int,int> pnt;
template <class T> inline void read(T &w) {
    w = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (w *= 10) += f*(c-'0');
}
int n, m; lnt ans[MAX_N+5];
int p[MAX_N+5], q[MAX_N+5]; pnt qry[MAX_N+5];
vector <pnt*> tr[MAX_N<<2]; pnt* sta[MAX_N+5];
struct operation {pnt p; int l, r;} opr[MAX_N+5];
pnt operator - (const pnt &a, const pnt &b) {return pnt(a.x-b.x, a.y-b.y);}
bool operator < (const pnt &a, const pnt &b) {return a.x == b.x ? a.y < b.y : a.x < b.x;}
lnt operator * (const pnt &a, const pnt &b) {return 1LL*a.x*b.x+1LL*a.y*b.y;}
lnt operator / (const pnt &a, const pnt &b) {return 1LL*a.x*b.y-1LL*a.y*b.x;}
bool cmp (const operation &a, const operation &b) {return a.p < b.p;}
void insert(int v, int s, int t, int l, int r, pnt *p) {
    if (s >= l && t <= r) {tr[v].push_back(p); return;}
    if (l <= mid) insert(v<<1, s, mid, l, r, p);
    if (r >= mid+1) insert(v<<1|1, mid+1, t, l, r, p);
}
void bi_solve(int v, int s, int t) {
    if (s == t) {
        p[s] = s;
        for (int i = 0; i < (int)tr[v].size(); i++)
            ans[s] = max(ans[s], qry[s]*(*tr[v][i]));
        return;
    }
    bi_solve(v<<1, s, mid), bi_solve(v<<1|1, mid+1, t);
    for (int i = s, p1 = s, p2 = mid+1; i <= t; i++)
        q[i] = (p2 > t || (p1 <= mid && qry[p[p1]]/qry[p[p2]] <= 0)) ? p[p1++] : p[p2++];
    for (int i = s; i <= t; i++) p[i] = q[i]; int tp = 0;
    for (int i = 0; i < (int)tr[v].size(); sta[++tp] = tr[v][i++])
        while (tp > 1 && ((*sta[tp])-(*sta[tp-1]))/((*tr[v][i])-(*sta[tp-1])) >= 0) tp--;
    if (!tp) return;
    for (int i = s, c = 1; i <= t; i++) {
        while (c < tp && qry[p[i]]*(*sta[c+1]) > qry[p[i]]*(*sta[c])) c++;
        ans[p[i]] = max(ans[p[i]], qry[p[i]]*(*sta[c]));
    }
}
int main() {
    int T; read(T);
    while (T--) {
        int opt; read(opt);
        if (opt == 1) {
            int xx, yy; read(xx), read(yy);
            opr[++n].p = pnt(xx, yy);
            opr[n].l = m+1, opr[n].r = -1;
        }
        if (opt == 2) {
            int id; read(id);
            opr[id].r = m;
        }
        if (opt == 3) {
            int xx, yy; read(xx), read(yy);
            qry[++m] = pnt(xx, yy);
        }
    }
    sort(opr+1, opr+n+1, cmp);
    for (int i = 1; i <= n; i++) {
        if (opr[i].r == -1) opr[i].r = m;
        if (opr[i].l > opr[i].r) continue;
        insert(1, 1, m, opr[i].l, opr[i].r, &opr[i].p);
    }
    bi_solve(1, 1, m);
    for (int i = 1; i <= m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}