凸包技巧/Convex Hull Trick

凸包技巧

参考：https://codeforces.com/blog/entry/63823

问题描述

我们想要快速地计算对于某个固定的$x$，下述算式集合中的最大值：

$$max_{j \in S}(k_j*x+b_j)$$

此外，插入一个新的$j$对应的算式到集合中也应该需要高效地完成。

思路

注意算式$k_j*x+b_j$的形式，它相当于斜率为$k_j$，与$y$轴交点为$k_j$的直线，所以这个问题就相当于是给定一系列直线与一个特定的$x$值，求在横坐标为$x$时，这一系列直线中最大的$y$值；如果将所有的直线画出来，你会发现最大值将是一个凸包的边缘，如下图所示：

一些观察到的结论

• 在凸包上的每一条线都在一段连续的$x$值区间内是最大值，相反，不在凸包上的线是无用的，这些线永远不会是最大值
• 在凸包上所有线的斜率都不一样，斜率的顺序同时决定了他们在凸包上的位置。斜率值较小的线在凸包上位于斜率比它大的线的左侧
  因此，一个可行的策略是只维护凸包上的线，而不保存那些无用的线

一个特定的问题

让我们考虑一个特定的问题：https://codeforces.com/contest/1083/problem/E

题目描述：有n个矩形（保证不存在矩形完全包含另一个矩形），4个顶点坐标分别为$(0,0),(x_i,0),(x_i,y_i),(0,y_i)$，对于每个矩形，都有一个$a_i$值，你的任务是：从$n$个矩形中选择任意个矩形，使得选中的矩形的总面积（重复面积只计算一次，即面积求并集）减去选中的矩形对应的$a_i$值最大

我们可以将$x$坐标从小到大排序，由于没有矩形包含其他的矩形，因此$y$坐标将从大到小排序。我们用$dp[i]$表示选了第$i$个矩形以及第$i$个矩形前面的某些矩形时，能够获得的最大分数，则：

$$dp[i]=max_{j<i}(dp[j]-x_j*y_i+x_i*y_i-a_i)= \\ max_{j<i}(dp[j]-x_j*y_i)+x_i*y_i-a_i$$

则上式中$max$内的部分满足$max_{j \in S}(k_j*x+b_j)$的形式，$-x_j$对应着斜率$k_j$，$dp[j]$对应着偏移$b_j$

思路：

• 在这个特定问题中，$x$坐标排序后是从小到大的，因此直线是按照斜率从大到小插入的
• 变量$y$是从大到小的，即查询的变量也是从大到小排好序的

实现查询和插入

查询

为了便于描述，我们仍然用$max_{j \in S}(k_j*x+b_j)$中的符号，用$k_j$表示斜率，用$x$表示变量，当查询$x=x_i$时，我们只需要比较斜率最大的直线和斜率次大的直线在$x_i$点的值，如果斜率最大的直线在$x_i$点的值小于斜率次大的直线，则将斜率最大的直线删除，重复该过程，直到斜率最大的直线在$x_i$点的值大于斜率次大的直线；因为当$x$逐渐增大时，斜率最大的直线最终总会变成最大值，而当$x$逐渐减小时，斜率最小的直线最终总会变成最大值，而上述问题中$x$是逐渐变小的，因此斜率大的直线如果在$x_i$点的值已经比斜率小的直线小了，那当$x$继续变小时，斜率大的直线再也不可能成为最大值了，因此可以删除，过程如下面的图示：

当$x=3$时，紫色的线斜率最大，但是值小于绿色的线，把紫色的线删除后，绿色的线斜率最大，同时值也是最大，本次查询结束

当$x=-3$时，将斜率最大但是值不是最大的直线一一删除，最终剩下的红色的线在该点取得最大值

插入

由于插入的直线斜率是按照顺序从大到小插入的，因此当插入一条新直线时，它的斜率比集合中所有直线的斜率都要小，我们采取的策略是，如果插入的直线与斜率最小的直线的交点的$x$值，比原本集合中斜率最小的直线和斜率次小的直线的交点的$x$值要大，则可以删除原集合中斜率最小的那条直线，重复该逻辑直到不满足上述条件后停止，如下图所示步骤，删除红色和蓝色的直线后，插入黑色虚线代表的直线：

代码实现

时间复杂度：$O(n+q)$，$n$是插入次数，$q$是查询次数

class Solution {
    struct Line {
        long long k, b;
        long long Eval(long long x) { return k * x + b; }
        long double IntersectX(Line l) { return (long double)(b - l.b) / (l.k - k); }
    };
    struct Rect {
        ll x,y,a;
        bool operator<(const Rect& r) const {
            return x < r.x;
        }
        friend istream &operator>>(istream &is, Rect &r) { return is >> r.x >> r.y >> r.a; }
    };
public:
    void Solve() {
        int n;
        while(cin>>n) {
            vector<Rect> rects(n); cin>>rects;
            sort(all(rects));

            deque<Line> lines;
            lines.emplace_back(Line{0, 0});
            ll ans = 0;
            rep(i,0,n) {
                while (lines.size() >= 2 && lines[lines.size() - 1].Eval(rects[i].y) <= lines[lines.size() - 2].Eval(rects[i].y)) {
                    lines.pop_back();
                }
                Line line{-rects[i].x, lines.back().Eval(rects[i].y) + rects[i].x * rects[i].y - rects[i].a};
                ans = max(ans, lines.back().Eval(rects[i].y) + rects[i].x * rects[i].y - rects[i].a);
                while (lines.size() >= 2 && lines[0].IntersectX(line) >= lines[0].IntersectX(lines[1])) {
                    lines.pop_front();
                }
                lines.emplace_front(line);
            }
            cout << ans << endl;
        }
    }
private:
};

一些其它情况

• 斜率插入和查询顺序与上述示例相反
  • 你可以修改上述逻辑，根据情况修改出入队列的头/尾
• 如果要求最小值而不是最大值
  • 可以修改插入和查询的逻辑
  • 或者将直线对x轴做镜像处理，即将斜率$m$和偏移$c$取相反数，然后复用之前的逻辑

更一般化的问题

• 直线是按照斜率排好序的顺序插入的
• 但是查询的位置可以是任意的
  为了解决这个问题，插入逻辑无需任何修改，然而我们在查询的时候不能够删除直线了，而由于在队列中的每条直线都在某个连续的范围内是最大值，且这个范围是有序的，起始点为该直线与前后直线的交点，因此我们可以使用二分查找来处理查询。

代码实现

时间复杂度：$O(n+q*log(n))$，$n$是插入次数，$q$是查询次数

int n;
while(cin>>n) {
    vector<Rect> rects(n); cin>>rects;
    sort(all(rects));
    deque<Line> lines;

    vector<int> ints(n);
    iota(ints.begin(), ints.end(), 0);
    auto cmp = [&lines](int idx, int x) { return lines[idx].IntersectX(lines[idx + 1]) < x; };

    lines.emplace_back(Line{0, 0});
    ll ans = 0;
    rep(i,0,n) {
        int idx = *lower_bound(ints.begin(), ints.begin() + lines.size() - 1, rects[i].y, cmp);
        Line line{-rects[i].x, lines[idx].Eval(rects[i].y) + rects[i].x * rects[i].y - rects[i].a};
        ans = max(ans, line.b);
        while (lines.size() >= 2 && lines[0].IntersectX(line) >= lines[0].IntersectX(lines[1])) {
            lines.pop_front();
        }
        lines.emplace_front(line);
    }
    cout << ans << endl;
}

初始问题

• 直线以任意的顺序插入
• 查询的位置按照任意的顺序

这个问题被称作“全动态”版本的凸包技巧（CHT），它可以使用有序集合来很方便的实现，例如c++中的std::set，思路是在集合中维护斜率的顺序。查询的时候，使用上一小节提到的二分查找。插入的时候，如果这条直线不处于凸包上，则不插入该条直线，如果处于凸包上，则删除处于插入直线两侧的所有无用直线（即插入该直线后不再处于凸包上的直线）。

代码实现

时间复杂度：$O((n+q)*log(n))$，$n$是插入次数，$q$是查询次数

struct Line {
    long long k, b;
    mutable long long intersect_x; // 集合中的直线按照斜率从小到大排序，该值表示本直线与下一条直线的交点的横坐标
    bool operator<(const Line& o) const { return k < o.k; } // 用于按照斜率排序
    bool operator<(long long x) const { return intersect_x < x; } // 用于二分查找
	long long Eval(long long x) { return k * x + b; } // 求直线在x点的y值
};

class LineContainer {
public:
	void Add(long long k, long long b) {
		Add(Line{k, b, 0});
	}
    void Add(const Line& line) {
        auto nxt = lines.insert(line), cur = nxt++, prev = cur;
		// 判断插入的直线后面的直线是否需要删除，如果删除则重新求相邻直线的交点
		while (Intersect(cur, nxt)) nxt = lines.erase(nxt);
		// 判断插入的直线本身是否需要删除，删除的话重新求相邻直线的交点
		if (prev != lines.begin() && Intersect(--prev, cur)) Intersect(prev, cur = lines.erase(cur));
		// 判断插入的直线前面的那一条直线是否需要删除，删除的话重新求相邻直线的交点
		while ((cur = prev) != lines.begin() && (--prev)->intersect_x >= cur->intersect_x)
			Intersect(prev, lines.erase(cur));
    }
	// 查找使得k*x+b最大的那条直线并返回最大的k*x+b
	long long Query(long long x) {
		assert(!lines.empty());
		auto l = lines.lower_bound(x);
		return l->k * x + l->b;
	}
private:
	// floored division, 因为两条直线之间的交点可能是小数，但是x是整数，因此小数部分永远不会取到
	// 所以求直线交点时只需要记录<=交点横坐标值的最大整数即可
	long long Div(long long a, long long b) {
		// 3/2 -> 1; -3/2 -> -2; 4/2 -> 2; -4/2 -> 2
		return a / b - ((a ^ b) < 0 && a % b);
	}
	// 求直线l1与l2的交点横坐标（向下取整），并判断是否需要删除直线l2
	bool Intersect(multiset<Line>::iterator l1, multiset<Line>::iterator l2) {
		if (l2 == lines.end()) {
			l1->intersect_x = numeric_limits<long long>::max();
			return false;
		}
		if (l1->k == l2->k) {
            l1->intersect_x = l1->b > l2->b ? numeric_limits<long long>::max()
                                            : numeric_limits<long long>::min();
        }
		else {
            l1->intersect_x = Div(l2->b - l1->b, l1->k - l2->k);
        }
		return l1->intersect_x >= l2->intersect_x;
	}

	multiset<Line, less<>> lines;
};

int n;
while(cin>>n) {
    vector<Rect> rects(n); cin>>rects;
    sort(all(rects));

    LineContainer lines;
    lines.Add(0, 0);
    ll ans = 0;
    rep(i,0,n) {
        Line line{-rects[i].x, lines.Query(rects[i].y) + rects[i].x * rects[i].y - rects[i].a};
        ans = max(ans, line.b);
        lines.Add(line);
    }

    cout << ans << endl;
}

例题

https://atcoder.jp/contests/dp/tasks/dp_z