Козак Вус та граф#101

Козак Вус та граф (Розбір)

У задачі три операції: питання «-та за номером вершина в компоненті», додавання ребра і відкат до стану після -ї операції. Саме відкат вимагає особливого підходу: система множин, що вміє роз'єднувати, — складна, а відкати — ні, якщо обробляти запити офлайн.

Дерево версій. Побудуємо дерево, вершинами якого є стани графа. Стан після операції отримується зі стану після операції i-1, крім випадку, коли -та операція — це відкат до : тоді стан після дорівнює стану після . Отже

\mathrm{par}(i) = \begin{cases} x, & \text{якщо } i\text{-та операція --- відкат до } x,\\ i-1, & \text{інакше.}\end{cases}

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

СНМ зі скасуванням. Щоб операції справді скасовувалися, у системі неперетинних множин не можна використовувати стиснення шляхів — лише об'єднання за розміром (чи рангом). Тоді одне об'єднання змінює рівно одну комірку parent та кілька лічильників, і скасування — це запис старих значень назад. Глибина дерева СНМ лишається \mathcal{O}(\log n), тож пошук кореня коштує \mathcal{O}(\log n).

-та за номером вершина. Це найцікавіше. Розіб'ємо номери вершин на блоки завдовжки . Для кожного кореня СНМ зберігатимемо масив

\mathrm{cnt}[\text{блок}][\text{корінь}] = \text{скільки вершин цього блоку належить цій компоненті}.

При об'єднанні додаємо масив меншої компоненти до більшої (чи навпаки — аби послідовно), при скасуванні — віднімаємо: на операцію.

Запит обробляється у два кроки:

  1. йдемо блоками зліва направо, віднімаючи , доки не знайдемо блок, у якому «сидить» шукана -та вершина — ;

  2. перебираємо вершини цього блоку по порядку й перевіряємо find(v) == root, доки не долічимо до — \mathcal{O}(d \log n).

Якщо ж розмір компоненти менший за , відповідь — розмір теж тримаємо в СНМ.

Баланс. Час — \mathcal{O}\bigl((n + q)(n/d + d\log n)\bigr), пам'ять — \mathcal{O}(n \cdot n/d). Класичний вибір d \approx \sqrt{n} дає \mathcal{O}((n+q)\sqrt{n}\log n) за часом, але \mathcal{O}(n\sqrt n) пам'яті — при n = 5 \cdot 10^5 це багато, тож на практиці блок беруть більшим за \sqrt n (наприклад, 2\sqrt n і більше), жертвуючи трохи часом заради пам'яті. Це і є головна інженерна частина задачі.

Дрібниці, на яких легко впасти. Обхід дерева версій має бути ітеративним — глибина сягає q = 5\cdot10^5. Ребро, обидва кінці якого вже в одній компоненті, нічого не змінює, але скасування все одно має про це знати (зберігайте прапорець «об'єднання відбулося»). І не забудьте, що операція відкату сама по собі не змінює графа — вона лише задає, від якого стану росте наступна гілка.