Олимпиадный тренинг

Задача . B. Внимательный Василий

Задача

$\text{[math]}$

Перед тем как стать успешным трейдером, Василий закончил университет. Во время его обучения произошел один случай, после которого Василий стал намного внимательнее слушать условия заданий для домашней работы. Далее приведено правильное формальное условие домашнего задания.

Дана строка $s$ длины $n$, состоящая только из символов «a», «b» и «c». Есть $q$ запросов вида ($pos, c$), который обозначает замену элемента строки $s$ на позиции $pos$ на символ $c$. После каждого запроса требуется вывести минимальное количество символов в строке, которые нужно заменить, чтобы строка не содержала строку «abc» в качестве подстроки. Правильной заменой символа является его изменение на символ «a», «b» или «c».

Строка $x$ является подстрокой $y$, если $x$ может быть получена из $y$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

Входные данные

Первая строка ввода содержит два целых числа $n$ и $q$ $(1 \le n, q \le 10^5)$ — длину строки и количество запросов соответственно.

Следующая строка ввода содержит строку $s$, состоящую из символов «a», «b» и «c».

Следующие $q$ строк содержат целое число $i$ и символ $c$ $(1 \le i \le n)$ — индекс и значение нового элемента строки соответственно. Гарантируется, что символ $c$ равен значению «a», «b» или «c».

Выходные данные

Для каждого запроса выведите минимальное количество символов, которые необходимо заменить, чтобы строка не содержала «abc» как подстроку.

Примечание

Рассмотрим состояния строки после каждого запроса:

$s =$ «abcabcabc». В этом случае можно сделать $3$ замены и получить, например, строку $s =$ «bbcaccabb». Эта строка не содержит «abc» как подотрезок.
$s =$ «bbcabcabc». В этом случае можно сделать $2$ замены и получить, например, строку $s =$ «bbcbbcbbc». Эта строка не содержит «abc» как подотрезок.
$s =$ «bccabcabc». В этом случае можно сделать $2$ замены и получить, например, строку $s =$ «bccbbcbbc». Эта строка не содержит «abc» как подотрезок.
$s =$ «bcaabcabc». В этом случае можно сделать $2$ замены и получить, например, строку $s =$ «bcabbcbbc». Эта строка не содержит «abc» как подотрезок.
$s =$ «bcabbcabc». В этом случае можно сделать $1$ замену и получить, например, строку $s =$ «bcabbcabb». Эта строка не содержит «abc» как подотрезок.
$s =$ «bcabccabc». В этом случае можно сделать $2$ замены и получить, например, строку $s =$ «bcabbcabb». Эта строка не содержит «abc» как подотрезок.
$s =$ «bcabccaac». В этом случае можно сделать $1$ замену и получить, например, строку $s =$ «bcabbcaac». Эта строка не содержит «abc» как подотрезок.
$s =$ «bcabccaab». В этом случае можно сделать $1$ замену и получить, например, строку $s =$ «bcabbcaab». Эта строка не содержит «abc» как подотрезок.
$s =$ «ccabccaab». В этом случае можно сделать $1$ замену и получить, например, строку $s =$ «ccabbcaab». Эта строка не содержит «abc» как подотрезок.
$s =$ «ccaaccaab». В этом случае строка не содержит «abc» как подотрезок, поэтому замен делать не требуется.

Примеры

№	Входные данные	Выходные данные
1	9 10 abcabcabc 1 a 1 b 2 c 3 a 4 b 5 c 8 a 9 b 1 c 4 a	3 2 2 2 1 2 1 1 1 0

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет