Ліхтарі#173

Ліхтарі (Розбір)

Спершу переформулюємо, що саме треба рахувати. У звіт потрапляють сегменти, які працюють зараз або працювали колись раніше. Тому нас цікавить об'єднання по часу множин робочих сегментів — множина, яка лише зростає.

У будь-який момент увімкнені ліхтарі утворюють максимальні суцільні блоки. Сегмент робочий тоді й лише тоді, коли він цілком лежить у якомусь такому блоці. Отже, кожен блок додає у звіт усі пари (l, r) з a \le l \le r \le b — «трикутник» T(a,b) розміру

|T(a,b)| = \frac{(b-a+1)(b-a+2)}{2}.

Далі два спостереження, що роблять задачу керованою.

Перше: подія «вимкнути» ніколи не змінює відповідь. Вимикання ліхтарів не може створити новий увімкнений блок, тому нових сегментів у звіт не додається — достатньо оновити поточний стан і повторити попередню відповідь.

Друге: досить зберігати лише максимальні за включенням блоки. Оскільки T(a,b) \subseteq T(a',b') рівносильно [a,b] \subseteq [a',b'], історія повністю описується антиланцюгом інтервалів (жоден не вкладений в інший).

Тепер алгоритм. Підтримуємо дві структури:

  • поточний стан ліхтарів — зручно як множину неперетинних відрізків однакового значення (так званий «Chtholly tree» на std::set) або дерево відрізків із присвоєнням на відрізку. Присвоєння на відрізку амортизовано працює за \mathcal{O}(\log N);

  • історичний антиланцюг — упорядкована множина максимальних інтервалів, що колись були увімкнені повністю.

Обробляючи подію «увімкнути », спочатку оновлюємо стан, а потім знаходимо максимальний увімкнений блок , що містить (розширюємо межі, доки сусідні ліхтарі увімкнені). Цей блок додаємо в антиланцюг: якщо він уже міститься в наявному інтервалі — нічого не змінюється; інакше видаляємо всі інтервали, які він поглинає, і вставляємо його. Кожен інтервал видаляється щонайбільше раз, тому сумарно це \mathcal{O}(Q \log Q).

Залишається швидко рахувати площу об'єднання трикутників. Для антиланцюга, впорядкованого за лівим кінцем, і ліві, і праві кінці зростають, а перетин сусідніх трикутників — це знову трикутник:

T(a_i, b_i) \cap T(a_{i+1}, b_{i+1}) = T(a_{i+1},\, b_i) \quad \text{при } a_{i+1} \le b_i.

Перетин несусідніх трикутників цілком міститься в проміжному, тому у формулі включень-виключень усі доданки, крім сусідніх пар, взаємно знищуються, і відповідь дорівнює просто

\sum_i |T(a_i, b_i)| \;-\; \sum_i |T(a_{i+1},\, b_i)|.

Цю суму зручно підтримувати інкрементно: при вставці або видаленні інтервалу змінюються лише його власний доданок і доданки двох сусідів.

Не забудьте врахувати початкову конфігурацію: її максимальні увімкнені блоки треба додати в антиланцюг до обробки першої події. Відповідь сягає порядку N^2/2, тобто потребує 64-бітного типу.