Convex hull trick
Рассмотрим следующую задачу:
Вася надувает воздушный шар. Каждую секунду он может либо дополнительно надуть шар, либо ничего не делать. Если он надувает шар в $i$-ю секунду, то радиус увеличивается на $a_i$, но после этого радиус будет уменьшаться на $b_i$ в секунду до следующего поддува. Найдите максимальный радиус шара, который можно получить за $n$ секунд.
Данную задачу можно решить с помощью динамического программирования. $dp_i$ — это наилучший радиус, который можно получить через $i$ секунд. Тогдв $$dp_i = \max_{j=1}^{i-1} dp_j + a_j - b_j \cdot (i - j) = \max_{j=1}^{i-1} (-b_j) \cdot i + (dp_j + a_j + b_j \cdot j) = \max_{j=1}^{i-1} A_j \cdot i + B_j$$ где $A, B$ зависят только от $j$. То есть можно считать, что нам надо найти минимальное значение среди линейных функций в точке $i$.
Convex hull
Будем поддерживать структуру данных, которая позволяет:
- добавить линейную функцию
- найти максимальное значение в данном множестве функций в точке $x$
Заметим, что данная функция будет иметь вид верхней огибающей. Пересечение новой линейной функции и огибающей не может имметь больше двух точек. Тогда нам надо научиться удалить из огибающей все прямые, которые из нее целиком пропали, а после добавить новую прямую и точки пересечения.
Такие операции действительно можно делать, если сложить все прямые в std::set
, находить бинпоиском те прямые, с которыми надо пересечь новую, и удалять все прямые между ними. Это будет работать за $O(n \log n)$, но пишется достаточно тяжело, и нужно редко. Кроме того, такую задачу можно решать, используя дерево Li Chao
Гораздо чаще в задаче бывает ограничение на монотонное изменение линейного коэффициента прямых (в нашем случае, $-b_i$). Тогда прямые нужно добавлять не в произвольное место структуры данных, а только в конец. В таком случае можно заменить std::set
на стек. Тогда находить точки пересечения можно не бинпоиском, а постепенным удалением "бесполезных" прямых. Таким образом, структуру можно реалиизовать с суммарным временем работы $O(n)$, если запросы по $x$ тоже были отсортированы (если не были, то отвечать на запрос бы будем за $O(\log n)$.
Реализация
В раиках данной реализации мы храним две величины: массив прямых $lines$ и массив точек изменений $pr$. Считаем, что $lines_i$ является минимальной на промежутке $[pr_i, pr_{i + 1}]$.
1 struct Line {
2 int k, m;
3 };
4
5 vector<int> pr; // если округлять точку пересечения вниз, то можно хранить их в целых числах
6 vector<Line> lines;
7
8 int get(int x) {
9 int l = 0;
10 int r = lines.size();
11 while (l + 1 < r) {
12 int mid = (l + r) / 2;
13 if (pr[mid] <= x) {
14 l = mid;
15 }
16 else {
17 r = mid;
18 }
19 }
20 return lines[l].k * x + lines[l].m;
21 }
22
23 void upd(Line line) {
24 while (lines.size() && line.k * pr.back() + line.m < lines.back().k * pr.back() + lines.back().m) {
25 pr.pop_back();
26 lines.pop_back();
27 }
28 int coord;
29 if (lines.empty()) {
30 coord = -INF;
31 } else {
32 coord = cross(line, lines.back());
33 }
34 pr.push_back(coord);
35 lines.push_back(line);
36 }
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s