chtrick.cpp

// "Convex hull trick": data structure that maintains a set of lines y = mx + b and allows querying the minimum value of mx_0 + b over all lines for some given x_0. Very useful in optimizing DP algorithms for partitioning problems.
// Tested against USACO MAR08 acquire. TODO: Test against IOI '02 Batch.
struct ConvexHullTrick {
	typedef long long LL;
	vector<LL> M;
	vector<LL> B;
	vector<double> left;
	ConvexHullTrick() {}
	bool bad(LL m1, LL b1, LL m2, LL b2, LL m3, LL b3) {
			// Careful, this may overflow
			return (b3-b1)*(m1-m2) < (b2-b1)*(m1-m3);
	}
	// Add a new line to the structure, y = mx + b.
	// Lines must be added in decreasing order of slope.
	void add(LL m, LL b) {
			while (M.size() >= 2 && bad(M[M.size()-2], B[B.size()-2], M.back(), B.back(), m, b)) {
					M.pop_back(); B.pop_back(); left.pop_back();
			}
			if (M.size() && M.back() == m) {
					if (B.back() > b) {
							M.pop_back(); B.pop_back(); left.pop_back();
					} else {
							return;
					}
			}
			if (M.size() == 0) {
					left.push_back(-numeric_limits<double>::infinity());
			} else {
					left.push_back((double)(b - B.back())/(M.back() - m));
			}
			M.push_back(m);
			B.push_back(b);
	}
	// Get the minimum value of mx + b among all lines in the structure.
	// There must be at least one line.
    LL query(LL x) {
                int i = upper_bound(left.begin(), left.end(), x) - left.begin();
                return M[i-1]*x + B[i-1];
        }
};