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