李超线段树（+合并）

struct node {
	int l, r; LL k, b;
} z[N*20];

void modify(int &p, int l, int r, LL k, LL b) {
	if (!p) {
		p = ++idx, z[p] = {0, 0, k, b};
		return;
	}
	int mid = (l+r)>>1;
	if (z[p].k*mid+z[p].b > k*mid+b) {
		swap(z[p].k, k), swap(z[p].b, b);
	}
	if (l == r) return;
	if (k > z[p].k) modify(z[p].l, l, mid, k, b);
	else if (k < z[p].k) modify(z[p].r, mid+1, r, k, b);
}

LL query(int p, int l, int r, int x) {
	if (!p) return 1e18;
	int mid = (l+r)>>1;
	LL res = z[p].k*x+z[p].b;
	if (x <= mid) res = min(res, query(z[p].l, l, mid, x));
	else res = min(res, query(z[p].r, mid+1, r, x));
	return res;
}

void merge(int &p, int q, int l, int r) {
	if (!p || !q) {
		p |= q; return;
	}
	int mid = (l+r)>>1;
	merge(z[p].l, z[q].l, l, mid);
	merge(z[p].r, z[q].r, mid+1, r);
	modify(p, l, r, z[q].k, z[q].b);
}