mex plus#528

mex plus (Розбір)

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

Далі — дві незалежні перешкоди, які й дають відповідь.

Перешкода 1: значення, потрібне обом. Нехай P = \min(\operatorname{mex} A, \operatorname{mex} B). Тоді кожне значення v < P має бути і в , і в . Але одне ребро віддає значення лише в один із масивів, тож таке мусить траплятися серед чисел пар щонайменше двічі. Звідси

P \;\le\; m_2 \;=\; \text{найменше значення, що трапляється не більше одного разу.}

Перешкода 2: деревні компоненти. Розглянемо зв'язну компоненту з вершин і ребер. Ребра дають рівно внесків у масив , тож не більше різних значень компоненти можуть опинитися в . Якщо компонента — дерево (E = V - 1), то хоча б одного значення в забракне; те саме окремо стосується . Пропускати вигідно найбільше значення компоненти, отже

\max(\operatorname{mex} A, \operatorname{mex} B) \;\le\; \min_{\substack{\text{компоненти-дерева } C}} \ \max_{v \in C} v .

Компонента з циклом (E \ge V) жодних обмежень не накладає — у ній орієнтацію можна підібрати так, щоб усі вершини отримали внесок. Не забудьте, що ізольована вершина теж дерево: значення, яке не трапляється жодного разу, автоматично потрапляє в цей мінімум.

Обидві межі досяжні одночасно, тому

\boxed{\ \operatorname{mex} A + \operatorname{mex} B \;=\; m_2 \;+\; \min_{\text{компоненти-дерева } C} \max_{v \in C} v\ }

Запити. Пари додаються й видаляються, тобто кожне ребро «живе» на певному відрізку часу. Це класична схема офлайнової динамічної зв'язності: будуємо рекурсію по відрізку часу [l, r]; на кожному рівні додаємо ребра, що покривають увесь відрізок, і стискаємо утворені компоненти в одну вершину, зберігаючи для неї максимум значень і позначку «дерево / з циклом». Компоненти, до яких більше не веде жодне «частинне» ребро, одразу віддають свій внесок у поточний мінімум і далі не передаються. У листках рекурсії лишається просто взяти мінімум.

Величину m_2 підтримувати ще простіше: тримаємо лічильник входжень кожного значення й чергу з пріоритетом із лінивим видаленням, куди кладемо значення, щойно його лічильник падає до одиниці, і викидаємо, щойно він сягає двійки.

Дрібниця про великі значення. Відповідь ніколи не перевищує n + q, тож усі значення, більші за цю межу, можна одразу «підтягнути» до n+q — це не змінює відповіді, зате робить розмір графа лінійним.

Складність — \mathcal{O}\bigl((n + q)\log(n+q)\bigr) з невеликою константою; рекурсію по часу краще писати без глибокої рекурсії по графу, або збільшити стек.