Задача C. Покраска забора ≡

Условие

Сегодня Евгений решил заняться покраской забора вокруг своего дома. Забор деревянный и состоит из N досок, причем каждая из них имеет ровно две соседние доски: 1 и N доска являются соседними.

Для того, чтобы покраска не стала рутинным занятием, Евгений решил красить доски не по порядку. За сегодня он планирует покрасить лишь Q досок, i-й из которых будет покрашена a_i доска.

После покраски очередной доски Евгений хочет определять количество непрерывных участков, состоящих только из непокрашенных досок. Причем, если две непокрашенных доски являются соседними, то они обязательно относятся к одному участку.

Требуется написать программу, которая по действиям Евгения определит количество непокрашенных участков после покраски очередной доски.

Формат входных данных

Первая строка содержит два целых числа N и Q — количество досок в заборе и количество досок, которые Евгений собирается покрасить, соответственно.

Вторая строка содержит Q различных целых чисел a_i — номер доски, которую Евгений будет красить i-й по счету.

Формат выходных данных

Выведите Q целых чисел через пробел — количество непрерывных непокрашенных участков после покраски i-й доски.

Ограничения

1 ≤ N ≤ 10⁹,

1 ≤ Q ≤ min(N, 10⁵)

1 ≤ a_i ≤ N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснения к примерам

В первом примере после покраски 2 доски получится один непрерывных участок (3, 4, 1), после покраски 4 доски — два участка (1) и (3), после покраски 3 — (1), а после покраски 1 — не покрашенных досок не останется.

Примеры тестов

4 4
2 4 3 1

1 2 1 0

8 6
2 4 7 1 3 8

1 2 3 3 2 1

10 10
2 7 1 9 3 10 5 6 8 4

1 2 2 3 3 2 3 2 1 0

Разбор

Частичные решения

Заведём массив u длины N, в котором u_i = false, если мы не покрасили i-ую доску и u_i = true если покрасили. После каждой покраски пометим свежепокрашенную доску в нашем массиве и пройдёмся по нему, считая ответ следующим образом:

Изначально у нас имеется один круговой непокрашенный участок длины N, начальный ответ равен 0 (т.к. первая покраска лишь превращает круговой участок в отрезок, а не разрезает его). Для каждого i (от 1 до N) проверяем следующее:

Если u_i = true и u_i − 1 = false, значит мы нашли конец непокрашенного отрезка, добавим 1 к ответу.

Такое решение работает за O(N ⋅ Q) и проходит 2 подзадачи.

Дальше следует заметить, что при покраске очередной доски она не влияет на остальные покрашенные, а значит нет нужды проверять все N досок. Для очередной покрашенной доски a проверим, если:

1) Обе доски рядом не покрашены (u_a − 1 = false И u_a + 1 = false), значит покраска данной доски разрезает сплошной непокрашенный участок, добавим 1 к ответу.

2) Одна доска рядом покрашена (u_a − 1 = true ИЛИ u_a + 1 = true), значит наша свежепокрашенная доска одной стороной прилегает к другой уже покрашенной, что не меняет ответ.

3) Обе доски рядом покрашены (u_a − 1 = true И u_a + 1 = true), значит мы закрасили непокрашенный участок длины 1, тем самым исключив его из ответа, отнимаем 1 от ответа.

Следует заметить, что для a = 1 и a = N значения a − 1 и a + 1 выходят за пределы [1; N], но так как забор круговой, мы должны прибавить/отнять N для получения корректного значения (т.е. для a = 1 a − 1 = N, для a = N a + 1 = 1).

Также стоит обратить внимание на случаи с N = 1 и N = 2, так как в них a − 1 = a + 1, что может приводить к неверному выбору случая в зависимости от реализации.

Такая оптимизация даст нам решение уже с O(Q), что проходит 3 подзадачи (в 4 подзадаче массив длиной 10⁹ не укладывается в ограничение по памяти).

Полное решение

а) Использовать вместо обычного массива ассоциативный (в C++ это будет map < int, int > ), нужно будет использовать всего O(Q) памяти при сложности алгоритма O(Q ⋅ log Q).

б) Альтернативный вариант полного решения - поддерживать все непокрашенные отрезки в виде пар [L_i; R_i], где L_i (R_i) - левая (правая) граница i-го непокрашенного отрезка. Изначально имеется только 1 отрезок [1; N].

Выберем структуру, позволяющую эффективно добавлять, удалять и искать в ней элементы в виде пар чисел (т.е. за O(log Q)), которые поддерживались бы в отсортированном виде (в C++ это set < pair < int, int >  > ).

При закрашивании доски a найдём отрезок [L_i; R_i] такой, чтобы L_i ≤ a ≤ R_i. Удалим его из структуры, после чего в зависимости от ситуации сделаем следующее:

1) Если (L_i = a ИЛИ R_i = a) И L_i ≠ R_i, то обрежем отрезок на 1 с нужного края и вставим обратно в структуру.

2) Если L_i = a И R_i = a, то мы полностью закрасили этот отрезок, ничего не делаем.

3) Если (L_i ≠ a И R_i ≠ a), то мы разрезали отрезок на два новых, вставим их в структуру ([L_i; a − 1] и [a + 1; R_i]).

Ответом будет являться количество отрезков в структуре (также стоит отнять 1, если в первом отрезке L = 1, а в последнем R = N, т.е. они являются одним сплошным отрезком).