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)$

#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;
}