---
tags: codebook
---

# Li Chao segment tree

**problem:** [vjudge link](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-1568)

constexpr int maxn = 5e4 + 5;
struct line {
	ld a, b;
	ld operator()(ld x) {return a * x + b;}
} arr[(maxn + 1) << 2];
bool operator<(line a, line b) {return a.a < b.a;}
#define m ((l+r)>>1)
void insert(line x, int i = 1, int l = 0, int r = maxn) {
	if (r - l == 1) {
		if (x(l) > arr[i](l))
			arr[i] = x;
		return;
	}
	line a = max(arr[i], x), b = min(arr[i], x);
	if (a(m) > b(m))
		arr[i] = a, insert(b, i << 1, l, m);
	else
		arr[i] = b, insert(a, i << 1 | 1, m, r);
}
ld query(int x, int i = 1, int l = 0, int r = maxn) {
	if (x < l || r <= x) return -numeric_limits<ld>::max();
	if (r - l == 1) return arr[i](x);
	return max({arr[i](x), query(x, i << 1, l, m), query(x, i << 1 | 1, m, r)});
}
#undef m
inline void solve() {
	int n; cin >> n;
	while (n--) {
		string op; cin >> op;
		if (op == "Project") {
			ld s, p; cin >> s >> p;
			insert(line{p, s - p});
		} else {
			int t; cin >> t;
			cout << (ll)query(t) / 100 << endl;
			// cout << query(t) << endl;
		}
	}
}

**problem:** [vjudge link](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-3165)

constexpr int maxn = 4e4 + 5;
// constexpr int maxn = 32;
struct line {
	ld a, b; int id;
	line(ld x = 0, ld y = 0, int i = 0): a(x), b(y), id(i) {}
	ld operator()(ld x) {return a * x + b;}
} arr[(maxn + 1) << 2];
bool operator<(line a, line b) {return a.a < b.a;}
#define m ((l+r)>>1)
void insert(int ql, int qr, line x, int i = 1, int l = 0, int r = maxn) {
	if (qr <= l || r <= ql) return;
	if (l < ql || qr < r) {
		insert(ql, qr, x, i << 1, l, m);
		insert(ql, qr, x, i << 1 | 1, m, r);
		return;
	}
	// debug(ql, qr, x.id, i, l, r);
	if (r - l == 1) {
		if (x(l) > arr[i](l))
			arr[i] = x;
		return;
	}
	line a = max(arr[i], x), b = min(arr[i], x);
	if (a(m) > b(m) || (a(m) == b(m) && a.id < b.id))
		arr[i] = a, insert(ql, qr, b, i << 1, l, m);
	else
		arr[i] = b, insert(ql, qr, a, i << 1 | 1, m, r);
}
P<ld, int> query(int x, int i = 1, int l = 0, int r = maxn) {
	if (r - l == 1) return {arr[i](x), arr[i].id};
	P<ld, int> tmp = (x < m ? query(x, i << 1, l, m) : query(x, i << 1 | 1, m, r));
	if (arr[i](x) < tmp.first || (arr[i](x) == tmp.first && tmp.second < arr[i].id))
		return tmp;
	else
		return {arr[i](x), arr[i].id};
}
#undef m
inline void solve() {
	int n; cin >> n;
	int lastans = 0, i = 0; ld a, b;
	while (n--) {
		int op, k, x0, y0, x1, y1;
		switch (cin >> op, op) {
		case 0:
			cin >> k, k = (k + lastans - 1) % 39989 + 1;
			cout << (lastans = query(k).second) << endl;
			// debug(lastans = query(k).second);
			break;
		case 1:
			cin >> x0 >> y0 >> x1 >> y1;
			x0 = (x0 + lastans - 1) % 39989 + 1;
			y0 = (y0 + lastans - 1) % 1000000000 + 1;
			x1 = (x1 + lastans - 1) % 39989 + 1;
			y1 = (y1 + lastans - 1) % 1000000000 + 1;
			// y - y0 = ((y1 - y0) / (x1 - x0))(x - x0)
			if (x1 - x0 == 0) {
				a = 0, b = max(y0, y1);
				insert(x0, x0 + 1, line(a, b, ++i));
				break;
			}
			a = (ld)(y1 - y0) / (x1 - x0);
			b = a * -x0 + y0;
			if (x0 > x1) swap(x0, x1);
			insert(x0, x1 + 1, line(a, b, ++i));
		}
	}
}