AtCoder Beginner Contest 246 Ex問題メモ

import numpy as np


class SegmentTreeInjectable:
    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            j = i >> 1
            tree[j] = func(tree[j << 1], tree[(j << 1) | 1])
            i >>= 1

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


mat_zero = np.array([
    [1, 0, 1, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
], np.int64)
mat_one = np.array([
    [1, 1, 0, 0],
    [0, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 0, 1],
], np.int64)
mat_ques = np.array([
    [2, 0, 0, 1],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 0, 0, 1],
], np.int64)
mat_identity = np.eye(4, dtype=np.int64)

MOD = 998244353

n, q = map(int, input().split())
s = input()
init_array = []
for c in s:
    if c == '0':
        init_array.append(mat_zero)
    elif c == '1':
        init_array.append(mat_one)
    else:
        init_array.append(mat_ques)

sgt = SegmentTreeInjectable.from_array(init_array, lambda: mat_identity, lambda a, b: a @ b % MOD)

for _ in range(q):
    x, c = input().split()
    x = int(x) - 1
    if c == '0':
        sgt.update(x, mat_zero)
    elif c == '1':
        sgt.update(x, mat_one)
    else:
        sgt.update(x, mat_ques)
    res = sgt.get_all()

    ans = (res[0].sum() - 1) % MOD
    print(ans)