https://contest.ucup.ac/contest/4207/problem/21380
Если убрать все детали, то задача следующая. Есть
n вершин, каждая характеризуется числами (x_i, A_i, B_i). Ребро между вершинами i и j стоит A_i * x_j + B_i. Формула получилась немного не симметричная, но на самом деле (A_i, B_i) такие, что расстояние в одну и другую сторону получаются одинаковые. Нужно на таком графе построить максимальное остовное дерево.Если вы внимательно читали предыдущие посты, то знаете, что когда нам дают какой-то неявный полный граф, в котором нужно находить MST, то нам нужен алгоритм Борувки. Тогда за логарифм итераций "для каждой вершины найти самую далекую не из текущей компоненты" мы сможем решить задачу.
Задача несколько усложняется тем, что
TL=1s, а сумма n может быть 5*10^5. Поэтому было бы неплохо делать каждую итерацию за линию, тогда суммарная сложность будет O(n log n). Оказывается так можно сделать!Как решать задачу, если нет условия на "не из текущей компоненты"? Тогда нужно построить верхнюю огибающую всех прямых
Ax+B. Отсортируем их по A, будем хранить стек, и добавлять их по одной. Потом посортируем все запросы по x и указателем будем искать нужную прямую. Все сортировки можно сделать заранее.Но в данной задаче нам нужно находить прямые не текущего цвета. Как обычно, будем хранить два максимума. Что это значит для выпуклой оболочки? Посмотроим оболочку не обращая внимание на цвет. Теперь для каждого наибольшего подотрезка оболочки одинакого цвета выкинем его и построим "вторую максимальную оболочку" из линий не этого цвета, которые лежат на том же интервале. Можно показать, что суммарный размер "вторых оболочек" будет
O(n).В итоге решение получается такое и проходит за ~300мс. А были времена, когда такое можно было сдавать не в дорешку...