An Array and Range Additions#224

An Array and Range Additions (Editorial)

Ключ до задачі — зрозуміти, що саме розрізняє елементи після операцій.

Виберемо для кожної операції довільне велике «загальне положення» $x$ . Тоді два елементи $a_{i}$ a_i та $a_{j}$ a_j стануть різними, якщо вони й так були різними, або якщо множини операцій, що їх накривають, не збігаються. Навпаки, якщо $a_{i} = a_{j}$ a_i = a_j і обидва накриті однаковим набором відрізків, вони назавжди залишаться рівними. Отже, задача формулюється так:

вибрати найменшу кількість відрізків так, щоб будь-які дві позиції з однаковим значенням мали різні набори накривних відрізків.

Назвемо цей набір підписом позиції. Підпис змінюється лише на кінцях відрізків, тому масив розпадається на суцільні блоки однакового підпису, і всередині кожного блоку значення мусять бути попарно різними.

Скільки блоків дають $m$ операцій? Кінців усього $2 m$ , тому блоків щонайбільше $2 m + 1$ 2m+1. Але найлівіший і найправіший блоки не накриті жодним відрізком — їхній підпис порожній, тобто спільний. Отже, різних підписів у «середині» щонайбільше $2 m - 1$ 2m - 1, а префікс і суфікс мусять бути разом вільними від повторів.

Цю межу досяжно: наприклад, для $m = 2$ m = 2 відрізки, що частково перекриваються, дають послідовність підписів

{}, {1}, {1, 2}, {2}, {},

\{\},\; \{1\},\; \{1,2\},\; \{2\},\; \{\},

тобто рівно три різні блоки посередині.

Звідси алгоритм. Переберемо, де закінчується «зовнішня» частина: беремо префікс $[0, p - 1]$ [0, p-1] і суфікс $[ptr + 1, n - 1]$ [\mathit{ptr}+1, n-1] так, щоб їхнє об'єднання не мало однакових значень. Оскільки зі зростанням $p$ суфікс може лише коротшати, усі такі пари перебираються двома вказівниками з лічильником входжень значень (перевірка «чи є повтор» — це максимум лічильника).

Для середини $[p, ptr]$ порахуємо $B$ — мінімальну кількість блоків, у кожному з яких значення різні. Це класична жадібність: блок тягнемо праворуч, доки не з'явиться повтор. Тоді потрібна кількість операцій дорівнює

⌊ \frac{B}{2} ⌋ + 1,

\left\lfloor \frac{B}{2} \right\rfloor + 1,

що є розв'язком нерівності $B \leq 2 m - 1$ B \le 2m - 1. Якщо середина порожня, відповідь нульова — масив уже придатний.

Щоб рахувати $B$ швидко для кожного $p$ , заздалегідь обчислимо $nxt [i]$ — початок наступного блоку, якщо жадібний блок починається в $i$ (знову два вказівники, тепер справа наліво), і побудуємо над цим масивом двійкові підйоми. Тоді кількість блоків на відрізку знаходиться за $O (lo g n)$ \mathcal{O}(\log n).

Відповідь — мінімум по всіх допустимих $p$ . Загальна складність — $O (n lo g n)$ \mathcal{O}(n \log n). Значення сягають $1 0^{9}$ 10^9, тому їх варто стиснути координатно, щоб лічильники поміщалися в масив.