codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1609B.md (3660B)


      1 Source: https://codeforces.com/problemset/problem/1609/B
      2 
      3 B. William the Vigilant
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 ![](https://espresso.codeforces.com/30320abd2fa30a4eb837420fbffbfdb8ddb36ce7.png) 
     22 
     23 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 the correct formal description of the homework assignment:
     24 
     25 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 substring. A valid replacement of a character is replacing it with "a", "b" or "c".
     26 
     27 A string $x$ is a substring of a string $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
     28 
     29 Input
     30 
     31 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.
     32 
     33 The second line contains the string $s$, consisting of characters "a", "b" and "c".
     34 
     35 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".
     36 
     37 Output
     38 
     39 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 substring.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 9 10
     47 abcabcabc
     48 1 a
     49 1 b
     50 2 c
     51 3 a
     52 4 b
     53 5 c
     54 8 a
     55 9 b
     56 1 c
     57 4 a
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 3
     64 2
     65 2
     66 2
     67 1
     68 2
     69 1
     70 1
     71 1
     72 0
     73 ```
     74 
     75 Note
     76 
     77 Let's consider the state of the string after each query:
     78 
     79 1. $s =$ "abcabcabc". In this case $3$ replacements can be performed to get, for instance, string $s =$ "bbcaccabb". This string does not contain "abc" as a substring.
     80 2. $s =$ "bbcabcabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bbcbbcbbc". This string does not contain "abc" as a substring.
     81 3. $s =$ "bccabcabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bccbbcbbc". This string does not contain "abc" as a substring.
     82 4. $s =$ "bcaabcabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bcabbcbbc". This string does not contain "abc" as a substring.
     83 5. $s =$ "bcabbcabc". In this case $1$ replacements can be performed to get, for instance, string $s =$ "bcabbcabb". This string does not contain "abc" as a substring.
     84 6. $s =$ "bcabccabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bcabbcabb". This string does not contain "abc" as a substring.
     85 7. $s =$ "bcabccaac". In this case $1$ replacements can be performed to get, for instance, string $s =$ "bcabbcaac". This string does not contain "abc" as a substring.
     86 8. $s =$ "bcabccaab". In this case $1$ replacements can be performed to get, for instance, string $s =$ "bcabbcaab". This string does not contain "abc" as a substring.
     87 9. $s =$ "ccabccaab". In this case $1$ replacements can be performed to get, for instance, string $s =$ "ccabbcaab". This string does not contain "abc" as a substring.
     88 10. $s =$ "ccaaccaab". In this case the string does not contain "abc" as a substring and no replacements are needed.