Рухомі точки#230

Рухомі точки (Розбір)

Спершу з'ясуємо, скільки коштує одне злиття. Щоб об'єднати дві сусідні крапки, які стоять на відстані $d$ , достатньо рухати одну з них назустріч іншій — це рівно $d$ секунд. Кожне таке злиття зменшує кількість крапок на одиницю.

Тепер ключове спостереження: злиття різних пар незалежні. Відсортуємо крапки й позначимо проміжки між сусідніми через $d_{1}, d_{2}, \dots, d_{n - 1}$ d_1, d_2, \ldots, d_{n-1}. Щоб «схлопнути» групу підряд розташованих крапок, треба витратити суму всіх проміжків усередині цієї групи. Тому будь-який план зводиться до вибору підмножини проміжків, які ми закриваємо; вартість — сума обраних проміжків, а виграш — по одній крапці за кожен.

Отже, щоб за час $t$ прибрати якнайбільше крапок, вигідно закривати найменші проміжки.

Звідси алгоритм:

відсортувати координати й прибрати дублікати — крапки, що вже збіглися, злиті задарма;
порахувати проміжки між сусідніми різними координатами;
відсортувати проміжки за зростанням і побудувати їхні префіксні суми;
на запит $t$ двійковим пошуком знайти найбільше $j$ з $d_{1} + \dots + d_{j} \leq t$ d_1 + \ldots + d_j \le t; відповідь — $(кількість різних крапок) - j$ (\text{кількість різних крапок}) - j.

Складність — $O (n lo g n + q lo g n)$ \mathcal{O}(n \log n + q \log n).

Не забудьте про дублікати у вхідних даних: без попереднього прибирання однакових координат серед проміжків з'являться нулі, і хоч відповідь від цього не зіпсується, початкову кількість крапок треба брати саме після злиття збіжних.