William The Oblivious  (Codeforces 1609E)
Tags: Others, matrices

  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.

Input: 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".

Output: 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.

Note: Let's consider the state of the string after each query:   $$$s = $$$"aaaaccccc". In this case the string does not contain "abc" as a subsequence and no replacements are needed. $$$s = $$$"aaabccccc". In this case 1 replacements can be performed to get, for instance, string $$$s = $$$"aaaaccccc". This string does not contain "abc" as a subsequence. $$$s = $$$"ababccccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$aaaaccccc". This string does not contain "abc" as a subsequence. $$$s = $$$"ababacccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaaaacccc". This string does not contain "abc" as a subsequence. $$$s = $$$"bbabacccc". In this case 1 replacements can be performed to get, for instance, string $$$s = $$$"bbacacccc". This string does not contain "abc" as a subsequence. $$$s = $$$"bbababccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"bbacacccc". This string does not contain "abc" as a subsequence. $$$s = $$$"bbabcbccc". In this case 1 replacements can be performed to get, for instance, string $$$s = $$$"bbcbcbccc". This string does not contain "abc" as a subsequence. $$$s = $$$"baabcbccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"bbbbcbccc". This string does not contain "abc" as a subsequence. $$$s = $$$"aaabcbccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaacccccc". This string does not contain "abc" as a subsequence. $$$s = $$$"aaababccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaacacccc". This string does not contain "abc" as a subsequence. $$$s = $$$"aaababccc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaacacccc". This string does not contain "abc" as a subsequence. $$$s = $$$"aaababbcc". In this case 2 replacements can be performed to get, for instance, string $$$s = $$$"aaababbbb". This string does not contain "abc" as a subsequence.

Sample Inputs:
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

Sample Outputs:
0
1
2
2
1
2
1
2
2
2
2
2

Solution (Python):
class SegmentTree:

    def __init__(self, arr, combinerFunction, isCommutative=True):
        self.n = len(arr)

        def cmb(a, b):
            if a == None:
                return b
            if b == None:
                return a
            return combinerFunction(a, b)
        self.cmb = cmb
        self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
        self.t = [None] * (2 * self.sz)
        for i in range(self.n):
            self.t[i + self.sz] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.pull(i)

    def pull(self, p):
        self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

    def update(self, idx, val):
        idx += self.sz
        self.t[idx] = val
        idx //= 2
        while idx > 0:
            self.pull(idx)
            idx //= 2

    def query(self, l, r):
        l += self.sz
        r += self.sz + 1
        a = b = None
        while l < r:
            if l % 2 == 1:
                a = self.cmb(a, self.t[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                b = self.cmb(self.t[r], b)
            l //= 2
            r //= 2
        return self.cmb(a, b)

def getMaxSegTree(arr):
    return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
    return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
    return SegmentTree(arr, lambda a, b: a + b, True)
baseNodeFactory = [(1, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0)]

def combinerFunction(l, r):
    return (l[0] + r[0], l[1] + r[1], l[2] + r[2], min(l[0] + r[3], l[3] + r[1]), min(l[1] + r[4], l[4] + r[2]), min(l[0] + r[5], l[3] + r[4], l[5] + r[2]))

def main():
    (n, q) = readIntArr()
    s = input()
    segArr = [baseNodeFactory[s[i] - ord('a')] for i in range(n)]
    segTree = SegmentTree(segArr, combinerFunction, False)
    allans = []
    for _ in range(q):
        (i, c) = input().split()
        i = int(i) - 1
        c = c[0] - ord('a')
        segTree.update(i, baseNodeFactory[c])
        node = segTree.query(0, n - 1)
        ans = node[5]
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(i, j, k):
    print('! {} {} {}'.format(i, j, k))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
class SegmentTree:

    def __init__(self, arr, combinerFunction, isCommutative=True):
        self.n = len(arr)

        def cmb(a, b):
            if a == None:
                return b
            if b == None:
                return a
            return combinerFunction(a, b)
        self.cmb = cmb
        self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
        self.t = [None] * (2 * self.sz)
        for i in range(self.n):
            self.t[i + self.sz] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.pull(i)

    def pull(self, p):
        self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

    def update(self, idx, val):
        idx += self.sz
        self.t[idx] = val
        idx //= 2
        while idx > 0:
            self.pull(idx)
            idx //= 2

    def query(self, l, r):
        l += self.sz
        r += self.sz + 1
        a = b = None
        while l < r:
            if l % 2 == 1:
                a = self.cmb(a, self.t[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                b = self.cmb(self.t[r], b)
            l //= 2
            r //= 2
        return self.cmb(a, b)

def getMaxSegTree(arr):
    return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
    return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
    return SegmentTree(arr, lambda a, b: a + b, True)

def baseNodeFactory(value):
    node = [0] * 6
    if value == 0:
        node[0] = 1
    elif value == 1:
        node[1] = 1
    else:
        node[2] = 1
    return node

def combinerFunction(l, r):
    node = [0] * 6
    node[0] = l[0] + r[0]
    node[1] = l[1] + r[1]
    node[2] = l[2] + r[2]
    node[3] = min(l[0] + r[3], l[3] + r[1])
    node[4] = min(l[1] + r[4], l[4] + r[2])
    node[5] = min(l[0] + r[5], l[3] + r[4], l[5] + r[2])
    return node

def main():
    (n, q) = readIntArr()
    s = input()
    a = [s[i] - ord('a') for i in range(n)]
    segArr = [baseNodeFactory(x) for x in a]
    segTree = SegmentTree(segArr, combinerFunction, False)
    allans = []
    for _ in range(q):
        (i, c) = input().split()
        i = int(i) - 1
        c = c[0] - ord('a')
        segTree.update(i, baseNodeFactory(c))
        node = segTree.query(0, n - 1)
        ans = node[5]
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(i, j, k):
    print('! {} {} {}'.format(i, j, k))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
class SegmentTree:

    def __init__(self, arr, combinerFunction, isCommutative=True):
        self.n = len(arr)

        def cmb(a, b):
            if a == None:
                return b
            if b == None:
                return a
            return combinerFunction(a, b)
        self.cmb = cmb
        self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
        self.t = [None] * (2 * self.sz)
        for i in range(self.n):
            self.t[i + self.sz] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.pull(i)

    def pull(self, p):
        self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

    def update(self, idx, val):
        idx += self.sz
        self.t[idx] = val
        idx //= 2
        while idx > 0:
            self.pull(idx)
            idx //= 2

    def query(self, l, r):
        l += self.sz
        r += self.sz + 1
        a = b = None
        while l < r:
            if l % 2 == 1:
                a = self.cmb(a, self.t[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                b = self.cmb(self.t[r], b)
            l //= 2
            r //= 2
        return self.cmb(a, b)

def getMaxSegTree(arr):
    return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
    return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
    return SegmentTree(arr, lambda a, b: a + b, True)

def baseNodeFactory(value):
    node = [0] * 6
    if value == 0:
        node[0] = 1
    elif value == 1:
        node[1] = 1
    else:
        node[2] = 1
    return tuple(node)

def combinerFunction(l, r):
    node = [0] * 6
    node[0] = l[0] + r[0]
    node[1] = l[1] + r[1]
    node[2] = l[2] + r[2]
    node[3] = min(l[0] + r[3], l[3] + r[1])
    node[4] = min(l[1] + r[4], l[4] + r[2])
    node[5] = min(l[0] + r[5], l[3] + r[4], l[5] + r[2])
    return tuple(node)

def main():
    (n, q) = readIntArr()
    s = input()
    a = [s[i] - ord('a') for i in range(n)]
    segArr = [baseNodeFactory(x) for x in a]
    segTree = SegmentTree(segArr, combinerFunction, False)
    allans = []
    for _ in range(q):
        (i, c) = input().split()
        i = int(i) - 1
        c = c[0] - ord('a')
        segTree.update(i, baseNodeFactory(c))
        node = segTree.query(0, n - 1)
        ans = node[5]
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(i, j, k):
    print('! {} {} {}'.format(i, j, k))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()