Untitled

 avatar
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