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

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 109,

1 ≤ Q ≤ min(N, 105)

1 ≤ ai ≤ N

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

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
NQ
1 21 1 ≤ N ≤ 102 1 ≤ Q ≤ min(N, 102)
2 25 1 ≤ N ≤ 105 1 ≤ Q ≤ min(N, 103) 1
3 31 1 ≤ N ≤ 105 1 ≤ Q ≤ min(N, 105) 1-2
4 23 1 ≤ N ≤ 109 1 ≤ Q ≤ min(N, 105) 1-3

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

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

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

Стандартный вход Стандартный выход
1
4 4
2 4 3 1
1 2 1 0
2
8 6
2 4 7 1 3 8
1 2 3 3 2 1
3
10 10
2 7 1 9 3 10 5 6 8 4
1 2 2 3 3 2 3 2 1 0

Разбор

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

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

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

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

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

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

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

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

3) Обе доски рядом покрашены (ua − 1 = true И ua + 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 подзадаче массив длиной 109 не укладывается в ограничение по памяти).

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

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

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

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

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

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

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

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

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

Подзадача Дополнительные ограничения Оценка времени работы решения
NQ
11 ≤ N ≤ 1021 ≤ Q ≤ min(N, 102)O(N2 ⋅ Q) — какое-нибудь квадратичное решение
21 ≤ N ≤ 1051 ≤ Q ≤ min(N, 103)O(N ⋅ Q) — решение с проверкой всех N досок
31 ≤ N ≤ 1051 ≤ Q ≤ min(N, 105)O(Q) (O(N) по памяти) — решение с проверкой одной текущей доски
41 ≤ N ≤ 1091 ≤ Q ≤ min(N, 105)O(Q ⋅ log Q) (O(Q) по памяти) — решение с ассоциативным массивом и проверкой одной текущей доски / решение с отрезками


0.252s 0.033s 13