Граф? Ви впевнені?#233

Граф? Ви впевнені? (Розбір)

Умова «кожне значення на шляху трапляється парну кількість разів» — це класичне запрошення до XOR-хешування.

Зіставимо кожному значенню $c$ випадкове $64$ -бітове число $h (c)$ (наприклад, через хеш-таблицю з генератором випадкових чисел). Тоді для будь-якої множини ребер XOR їхніх хешів дорівнює нулю з переважною ймовірністю саме тоді, коли кожне значення трапляється парну кількість разів: значення, що входять двічі, взаємно знищуються, а випадкові хеші «випадково» занулитися майже не можуть.

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

Основна величина. Для кожної вершини $v$ зберігатимемо $hs [v]$ — XOR хешів усіх ребер на шляху від $v$ до кореня її компоненти. Тоді XOR уздовж шляху між $u$ і $v$ однієї компоненти дорівнює

hs [u] \oplus hs [v],

\mathrm{hs}[u] \oplus \mathrm{hs}[v],

бо спільна частина до кореня взаємно знищується. Отже, шлях гарний тоді й лише тоді, коли $hs [u] = hs [v]$ \mathrm{hs}[u] = \mathrm{hs}[v].

Запити.

Тип 2 — якщо вершини в різних компонентах, виводимо $- 1$ ; інакше порівнюємо $hs [u]$ і $hs [v]$ .
Тип 3 — кількість гарних пар у компоненті дорівнює $\sum_{x} (2 cnt [ x ])$ \sum_{x} \binom{\mathrm{cnt}[x]}{2}, де $cnt [x]$ — скільки вершин компоненти мають значення $hs = x$ \mathrm{hs} = x. Підтримуємо цю суму для кожного кореня.
Тип 4 — те саме, але сумарно по всьому лісу; тримаємо один глобальний лічильник.

Додавання ребра. З'єднуючи компоненти, треба перерахувати $hs$ у всіх вершинах однієї з них: якщо приєднуємо компоненту $B$ до кореня компоненти $A$ через ребро зі значенням $c$ , то всі $hs$ вершин $B$ треба поXORити зі сталою $δ$ , що визначається $h (c)$ і поточними значеннями кінців ребра.

Щоб це було швидко, застосуємо об'єднання меншого до більшого: для кожного кореня тримаємо список його вершин і хеш-таблицю $cnt$ , а переносимо завжди меншу компоненту. Кожна вершина змінює компоненту щонайбільше $O (lo g n)$ \mathcal{O}(\log n) разів, тому загальна робота — $O (n lo g n)$ \mathcal{O}(n \log n) переносів.

Під час переносу кожної вершини акуратно оновлюємо три величини: прибираємо її внесок $(2 \cdot)$ \binom{\cdot}{2} зі старої компоненти, змінюємо $hs$ , додаємо внесок у нову компоненту — і паралельно правимо глобальний лічильник.

Загальна складність — $O ((n + q) lo g n)$ \mathcal{O}((n + q)\log n) у середньому. Беріть $64$ -бітні хеші: з $32$ -бітними ймовірність колізії на такій кількості пар уже помітна.