Спершу переформулюємо, що саме треба рахувати. У звіт потрапляють сегменти, які працюють зараз або працювали колись раніше. Тому нас цікавить об'єднання по часу множин робочих сегментів — множина, яка лише зростає.
У будь-який момент увімкнені ліхтарі утворюють максимальні суцільні блоки. Сегмент робочий тоді й лише тоді, коли він цілком лежить у якомусь такому блоці. Отже, кожен блок додає у звіт усі пари (l, r) з a \le l \le r \le b — «трикутник» T(a,b) розміру
Далі два спостереження, що роблять задачу керованою.
Перше: подія «вимкнути» ніколи не змінює відповідь. Вимикання ліхтарів не може створити новий увімкнений блок, тому нових сегментів у звіт не додається — достатньо оновити поточний стан і повторити попередню відповідь.
Друге: досить зберігати лише максимальні за включенням блоки. Оскільки 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).
Залишається швидко рахувати площу об'єднання трикутників. Для антиланцюга, впорядкованого за лівим кінцем, і ліві, і праві кінці зростають, а перетин сусідніх трикутників — це знову трикутник:
Перетин несусідніх трикутників цілком міститься в проміжному, тому у формулі включень-виключень усі доданки, крім сусідніх пар, взаємно знищуються, і відповідь дорівнює просто
Цю суму зручно підтримувати інкрементно: при вставці або видаленні інтервалу змінюються лише його власний доданок і доданки двох сусідів.
Не забудьте врахувати початкову конфігурацію: її максимальні увімкнені блоки треба додати в антиланцюг до обробки першої події. Відповідь сягає порядку N^2/2, тобто потребує 64-бітного типу.