Kinetic Segment Tree

boj12795.cpp

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXT = 530000;
const lint inf = 4e18;

struct line {
	lint A, B;
	lint eval(lint x) { return A * x + B; }
	// returns the x-intercept of intersection "strictly" larger than T
	lint cross_after(line &x, lint T) {
		if (x.A == A) {
			return inf;
		}
		lint up = x.B - B;
		lint dn = A - x.A;
		if (dn < 0) {
			dn *= -1;
			up *= -1;
		}
		lint incep = (up <= 0 ? -((-up) / dn) : (up + dn - 1) / dn);
		if (incep > T)
			return incep;
		return inf;
	}
};

struct kst { // min kinetic segment tree
	line tree[MAXT];
	lint melt[MAXT], T;
	int n;
	void pull(int p) {
		lint l = tree[2 * p].eval(T);
		lint r = tree[2 * p + 1].eval(T);
		tree[p] = (l < r || (l == r && tree[2 * p].A < tree[2 * p + 1].A)) ? tree[2 * p] : tree[2 * p + 1];
		melt[p] = min({melt[2 * p], melt[2 * p + 1], tree[2 * p].cross_after(tree[2 * p + 1], T)});
	}
	void init(int s, int e, int p, vector<line> &l) {
		if (s == e) {
			tree[p] = l[s];
			melt[p] = inf;
			return;
		}
		int m = (s + e) / 2;
		init(s, m, 2 * p, l);
		init(m + 1, e, 2 * p + 1, l);
        pull(p);
	}
	void update(int pos, line v, int s, int e, int p = 1) {
		if (s == e) {
			tree[p] = v;
			return;
		}
		int m = (s + e) / 2;
		if (pos <= m)
			update(pos, v, s, m, 2 * p);
		else
			update(pos, v, m + 1, e, 2 * p + 1);
		pull(p);
	}
	lint query(int s, int e, int ps, int pe, int p = 1) {
		if (e < ps || pe < s)
			return inf;
		if (s <= ps && pe <= e)
			return tree[p].eval(T);
		int pm = (ps + pe) / 2;
		return min(query(s, e, ps, pm, 2 * p), query(s, e, pm + 1, pe, 2 * p + 1));
	}
	void heaten(int s, int e, int p) {
		if (melt[p] > T)
			return;
		int m = (s + e) / 2;
		heaten(s, m, 2 * p);
		heaten(m + 1, e, 2 * p + 1);
		pull(p);
	}
	void init(vector<line> &l, lint _T) {
		n = sz(l);
		T = _T;
		init(0, n - 1, 1, l);
	}
	void heaten(lint _T) {
		assert(T <= _T);
		T = _T;
		heaten(0, n - 1, 1);
	}
} kst;

struct query {
	int s, e;
	lint t;
	int idx;
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin >> q;
	vector<query> quer;
	vector<line> v;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			lint p, q;
			cin >> p >> q;
			v.push_back({-p, -q});
		} else {
			lint t;
			cin >> t;
			int s = sz(quer);
			quer.push_back({0, sz(v), t, s});
		}
	}
	kst.init(v, -2e12);
	sort(all(quer), [&](const query &a, const query &b) { return a.t < b.t; });
	vector<lint> ans(sz(quer));
	for (auto &x : quer) {
		kst.heaten(x.t);
		ans[x.idx] = -kst.query(x.s, x.e - 1, 0, sz(v) - 1);
	}
	for (auto &x : ans)
		cout << x << "\n";
}