Untitled
unknown
plain_text
4 months ago
3.4 kB
3
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long int tt, tc; const int MAXA = 2e6 + 9; const int DELTA = 1e6; bool maxval; struct Line { ll m, c; Line() {} Line(ll m, ll c) : m(m), c(c) {} ll evaluate(ll x) { return (m * x + c) * (maxval ? -1 : 1); } }; struct Node { Line top; int left = -1, right = -1; Node() {} Node(ll m, ll c) : top(Line(m,c)) {} Node (Line curr) : top(curr) {} ll evaluate(ll x) { return top.evaluate(x); } }; vector<Node> Tree; const ll INF = 1e18; vector<vector<pair<int, Line>>> st; void addline(Line toadd, ll l, ll r, int idx) { ll mid = (l+r)/2; Line& top = Tree[idx].top; if (top.evaluate(mid) > toadd.evaluate(mid)) { st.back().emplace_back(idx, top); swap(top, toadd); } if (r-l <= 1) return; if (top.evaluate(l) > toadd.evaluate(l)) { if (Tree[idx].left == -1) { Tree[idx].left = Tree.size(); Tree.emplace_back(top); } addline(toadd,l,mid,Tree[idx].left); } else{ if (Tree[idx].right == -1) { Tree[idx].right = Tree.size(); Tree.emplace_back(top); } addline(toadd,mid,r,Tree[idx].right); } } void addline(ll m,ll c) { addline(Line(m,c), 0, MAXA + 1, 0); } ll query(ll x,ll l,ll r,int idx) { if (idx==-1) return INF; if (x<l || x>=r) return Tree[idx].evaluate(x); if (r-l <= 1) return Tree[idx].evaluate(x); ll mid = (l+r)/2; return min({Tree[idx].evaluate(x), query(x,l,mid,Tree[idx].left), query(x,mid,r,Tree[idx].right)}); } ll query(ll x) { return min(Tree[0].evaluate(x), query(x,0,MAXA+1,0)) * (maxval ? -1 : 1); } void clear() { Tree.clear(); Tree.emplace_back(0,INF * (maxval ? -1 : 1)); } void roll_back() { auto V = st.back(); st.pop_back(); reverse(V.begin(), V.end()); for (auto& [v, X] : V) { swap(Tree[v].top, X); } } void solve() { maxval = 1; clear(); int n = 1; int index = 0; vector<vector<int>> g(n); vector<ll> X(n), Y(n); vector<pair<int, ll>> ask; // first is vertex, second is value int q; cin >> q; while (q--) { int type; cin >> type; if (type == 1) { cin >> index; } else if (type == 2) { ll XX, YY; cin >> XX >> YY; int new_index; cin >> new_index; g[index].push_back(new_index); X.push_back(XX); Y.push_back(YY); n++; g.push_back(vector<int>()); index = new_index; } else { ll V; cin >> V; ask.emplace_back(index, V); } } vector<vector<int>> queries(n); q = ask.size(); vector<ll> query_ans(q); for (int i = 0; i < q; i++) { queries[ask[i].first].push_back(i); } function<void(int)> dfs = [&](int v) { st.push_back(vector<pair<int, Line>>()); addline(X[v], Y[v]); for (int quer : queries[v]) query_ans[quer] = query(ask[quer].second); for (int u : g[v]) dfs(u); roll_back(); }; for (ll val : query_ans) cout << val << "\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