Gra-gra-graph#179

Gra-gra-graph (Editorial)

Спершу розберемо саму гру, і виявиться, що вона зовсім проста.

Позначимо через $s = r - l + 1$ s = r - l + 1 кількість вершин підгри, через $M = (2 s)$ M = \binom{s}{2} — максимально можливу кількість ребер, а через $D = M - e$ D = M - e — кількість відсутніх ребер у поточному графі.

Перший гравець виграє, щойно граф стає повним, тобто щойно $D = 0$ D = 0. Кожен хід змінює $D$ рівно на одиницю: додавання ребра зменшує, видалення — збільшує.

Якщо $D = 0$ D = 0 вже на старті, перший гравець виграв одразу.
Якщо $D = 1$ D = 1, Антон своїм першим ходом додає єдине відсутнє ребро й виграє.
Якщо $D \geq 2$ D \ge 2, у Антона немає шансів: скільки б ребер він не додавав, суперник щоразу видаляє щойно додане, повертаючи $D$ до попереднього значення. Оскільки після ходу Антона лишається $D - 1 \geq 1$ D - 1 \ge 1 відсутніх ребер, граф ніколи не стає повним, і гра триває вічно — перемагає другий гравець.

Отже, перший гравець виграє на відрізку $[l, r]$ [l, r] тоді й лише тоді, коли індукований підграф є повним або повним без одного ребра:

e (l, r) \geq (2 s) - 1.

e(l, r) \ge \binom{s}{2} - 1.

Тепер підрахунок. Ключове спостереження — монотонність: додавання нової вершини до відрізка ніколи не зменшує кількість відсутніх ребер, бо всі попередні «дірки» залишаються. Тому для фіксованого $l$ множина придатних $r$ — це префікс: розширюємо $r$ , доки $D \leq 1$ D \le 1, і зупиняємось назавжди, щойно $D \geq 2$ D \ge 2.

Заодно це дає межу на довжину: майже повний підграф на $s$ вершинах потребує щонайменше $(2 s) - 1$ \binom{s}{2} - 1 ребер, тому $s = O (m)$ s = \mathcal{O}(\sqrt{m}) — відрізки короткі.

Реалізація: ідемо $l$ від $n$ до $1$ і розширюємо $r$ ; додаючи вершину $r$ , треба дізнатися, скільки її сусідів уже лежать у $[l, r - 1]$ [l, r-1]. Це класичний запит «скільки елементів у діапазоні», який обробляє дерево Фенвіка над номерами вершин. Кожне додавання оновлює лічильник ребер усередині відрізка, і ми одразу перевіряємо умову.

Складність — $O ((n + кількість придатних відрізків) lo g n)$ \mathcal{O}\bigl((n + \text{кількість придатних відрізків}) \log n\bigr). Відповідь може сягати $(2 n + 1)$ \binom{n+1}{2}, тому 64-бітний тип обов'язковий.