Untitled
unknown
plain_text
4 months ago
3.1 kB
7
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long int tt, tc; #define ll long long #define eb emplace_back #define nl '\n' #define deb(x) cerr << #x" = " << x << nl #define in() ( { int a ; scanf("%d", &a); a; } ) const int N = 1e5 + 9; const int mod = 1e9 + 7; struct Line { ll k, d; ll eval(ll x) { return k * x + d; } }; struct LiChaoNode { Line line; int l, r; LiChaoNode() { line = Line({0, numeric_limits<long long>::max() / 2}); l = 0, r = 0; } LiChaoNode(Line line) : line(line), l(0), r(0) {} } t[50 * N]; int T; int upd(int pre, Line nw, int l, int r) { int m = (l + r) / 2; int id = ++T; t[id].line = t[pre].line; bool lef = nw.eval(l) < t[id].line.eval(l); bool mid = nw.eval(m) < t[id].line.eval(m); if(mid) swap(t[id].line, nw); if(l == r) return id; if(lef != mid) { if(!t[pre].l) t[id].l = ++T, t[T] = LiChaoNode(nw); else t[id].l = upd(t[pre].l, nw, l, m); t[id].r = t[pre].r; } else { if(!t[pre].r) t[id].r = ++T, t[T] = LiChaoNode(nw); else t[id].r = upd(t[pre].r, nw, m + 1, r); t[id].l = t[pre].l; } return id; } ll Query(int cur, int x, int l, int r) { ll val = t[cur].line.eval(x); int m = (l + r) / 2; if(l < r) { if(x <= m && t[cur].l) val = min(val, Query(t[cur].l, x, l, m)); if(x > m && t[cur].r) val = min(val, Query(t[cur].r, x, m + 1, r)); } return val; } struct PersistentLiChaoTree { int L, R; vector<int> roots; PersistentLiChaoTree() { roots = {1}; T = 1; L = -1e9; R = 1e9; } PersistentLiChaoTree(int L, int R) : L(L), R(R) { T = 1; roots.push_back(1); } void add_line(Line line, int i) { int root = upd(roots[i], line, L, R); roots.push_back(root); } ll query(int i, int x) { return Query(roots[i], x, L, R); } } lt; const int MAX = 2e6 + 9; vector<int> g[MAX]; vector<int> queries[MAX]; int query_ans[MAX]; ll query_val[MAX]; ll A[MAX], B[MAX]; int root_idx[MAX]; void dfs(int v, int par_idx) { Line line; line.k = -A[v], line.d = -B[v]; lt.add_line(line, par_idx); int my_index = lt.roots.size() - 1; for (int query : queries[v]) query_ans[query] = -lt.query(my_index, query_val[query]); for (int u : g[v]) dfs(u, my_index); } void solve() { int q; cin >> q; int index = 0; int query_index = 0; while (q--) { int type; cin >> type; if (type == 1) cin >> index; else if (type == 2) { int X, Y, new_index; cin >> X >> Y >> new_index; A[new_index] = X; B[new_index] = Y; g[index].push_back(new_index); index = new_index; } else { ll V; cin >> V; query_val[query_index] = V; queries[index].push_back(query_index); query_index++; } } dfs(0, 0); for (int i = 0; i < query_index; i++) cout << query_ans[i] << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); tt = 1, tc = 1; // cin >> tt; while (tt--) { solve(); tc++; } }
Editor is loading...
Leave a Comment