Козак Вус і Потоколяндія#135

Козак Вус і Потоколяндія (Розбір)

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

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

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

Побудуємо стан після всіх днів (граф без видалених доріг, з уже зменшеними населеннями) і підемо назад у часі, скасовуючи події:

  • скасування видалення дороги — це додавання ребра, тобто звичайне об'єднання в СНМ;

  • скасування від'їзду — це додавання k_i мешканців до відповідної компоненти.

Обидві операції лише збільшують суми, що знову підтверджує монотонність.

Щоб уміти питати «яка сума компоненти вершини на день », скористаємось СНМ із мітками часу. Об'єднуючи компоненти, ми не робимо стиснення шляхів, а лише підвішуємо меншу до більшої, запам'ятовуючи момент об'єднання. Крім того, для кожного кореня зберігаємо історію його суми — список пар «(момент, нова сума)», який за побудовою впорядкований за часом.

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

Оскільки об'єднання йде за розміром, глибина дерева СНМ — \mathcal{O}(\log n), тому один запит коштує \mathcal{O}(\log n), а разом із двійковим пошуком по дню — \mathcal{O}(\log^2) на запит користувача.

Стежте за типами: сумарна кількість мешканців може бути великою, тому 64-бітний тип обов'язковий. І не забудьте окремий випадок, коли умова не виконується навіть у нульовий день — тоді відповіді немає.