A14736 | $William The Oblivious$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

![](/uploads/acgo/image/932ef339398f472c_6a65cc93132d.jpeg)Before becoming a successful trader William got a university degree. During his education an interesting situation happened, after which William started to listen to homework assignments much more attentively. What follows is a formal description of the homework assignment as William heard it: You are given a string $s$ of length $n$ only consisting of characters "a", "b" and "c". There are $q$ queries of format ( $pos, c$ ), meaning replacing the element of string $s$ at position $pos$ with character $c$ . After each query you must output the minimal number of characters in the string, which have to be replaced, so that the string doesn't contain string "abc" as a subsequence. A valid replacement of a character is replacing it with "a", "b" or "c". A string $x$ is said to be a subsequence of string $y$ if $x$ can be obtained from $y$ by deleting some characters without changing the ordering of the remaining characters.

The first line contains two integers $n$ and $q$ $(1 \le n, q \le 10^5)$ , the length of the string and the number of queries, respectively. The second line contains the string $s$ , consisting of characters "a", "b" and "c". Each of the next $q$ lines contains an integer $i$ and character $c$ $(1 \le i \le n)$ , index and the value of the new item in the string, respectively. It is guaranteed that character's $c$ value is "a", "b" or "c".

For each query output the minimal number of characters that would have to be replaced so that the string doesn't contain "abc" as a subsequence.

输入 #1

9 12
aaabccccc
4 a
4 b
2 b
5 a
1 b
6 b
5 c
2 a
1 a
5 a
6 b
7 b

输出 #1

C++ 编辑器

输入

输出