結果

問題 No.2611 Count 01
ユーザー MitarushiMitarushi
提出日時 2024-01-19 18:29:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,855 ms / 6,000 ms
コード長 4,956 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 205,944 KB
最終ジャッジ日時 2024-09-28 03:44:38
合計ジャッジ時間 77,971 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,376 KB
testcase_01 AC 42 ms
53,632 KB
testcase_02 AC 51 ms
61,568 KB
testcase_03 AC 3,700 ms
204,888 KB
testcase_04 AC 3,720 ms
204,508 KB
testcase_05 AC 3,731 ms
205,124 KB
testcase_06 AC 3,719 ms
205,384 KB
testcase_07 AC 3,607 ms
204,720 KB
testcase_08 AC 3,817 ms
205,944 KB
testcase_09 AC 3,770 ms
205,696 KB
testcase_10 AC 3,720 ms
205,404 KB
testcase_11 AC 3,855 ms
205,624 KB
testcase_12 AC 3,670 ms
205,676 KB
testcase_13 AC 3,672 ms
204,828 KB
testcase_14 AC 3,766 ms
205,088 KB
testcase_15 AC 3,773 ms
205,624 KB
testcase_16 AC 3,846 ms
205,252 KB
testcase_17 AC 3,759 ms
205,304 KB
testcase_18 AC 3,797 ms
205,332 KB
testcase_19 AC 3,807 ms
205,468 KB
testcase_20 AC 3,703 ms
205,652 KB
testcase_21 AC 3,779 ms
204,952 KB
testcase_22 AC 3,720 ms
205,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import array, sys

input = sys.stdin.readline

class SegmentTree:
    def __init__(self, n, e):
        n2 = 1
        while n2 < n:
            n2 *= 2
        self.n = n2
        self.data = [e] * (n2 * 2)

    def build(self, a):
        for i, x in enumerate(a):
            self.data[i + self.n] = x
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.data[i * 2] + self.data[i * 2 + 1]

    def update(self, i, x):
        k = i + self.n
        self.data[k] = x
        while k > 1:
            k //= 2
            self.data[k] = self.data[k * 2] + self.data[k * 2 + 1]

    def query(self, l, r, ls, rs):
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                ls += self.data[l]
                l += 1
            if r & 1:
                r -= 1
                rs = self.data[r] + rs
            l //= 2
            r //= 2
        return ls + rs


MOD = 998244353

class Vec:
    def __init__(self, a):
        self.a = a

    def __add__(self, other):
        if other.a is None:
            return self
        if self.a is None:
            return other
        if isinstance(other, Matrix):
            result = self.a[:]
            result[0] += self.a[1] * other.a[0]
            result[0] += self.a[2] * other.a[1]
            result[1] += self.a[2] * other.a[2]
            result[0] += self.a[3] * other.a[3]
            result[1] += self.a[3] * other.a[4]
            result[2] += self.a[3] * other.a[5]
            result[0] += self.a[4] * other.a[6]
            result[1] += self.a[4] * other.a[7]
            result[2] += self.a[4] * other.a[8]
            result[3] += self.a[4] * other.a[9]
            result[0] += self.a[5] * other.a[10]
            result[1] += self.a[5] * other.a[11]
            result[2] += self.a[5] * other.a[12]
            result[3] += self.a[5] * other.a[13]
            result[4] += self.a[5] * other.a[14]
            for i in range(len(self.a)):
                result[i] %= MOD
            return Vec(result)
        return sum(x * y for x, y in zip(self.a, other.a)) % MOD

class Matrix:
    size = 6
    def __init__(self, a):
        self.a = a

    def __add__(self, other):
        if other.a is None:
            return self
        if self.a is None:
            return other
        if isinstance(other, Vec):
            result = other.a[:]
            result[1] += self.a[0] * other.a[0]
            result[2] += self.a[1] * other.a[0]
            result[2] += self.a[2] * other.a[1]
            result[3] += self.a[3] * other.a[0]
            result[3] += self.a[4] * other.a[1]
            result[3] += self.a[5] * other.a[2]
            result[4] += self.a[6] * other.a[0]
            result[4] += self.a[7] * other.a[1]
            result[4] += self.a[8] * other.a[2]
            result[4] += self.a[9] * other.a[3]
            result[5] += self.a[10] * other.a[0]
            result[5] += self.a[11] * other.a[1]
            result[5] += self.a[12] * other.a[2]
            result[5] += self.a[13] * other.a[3]
            result[5] += self.a[14] * other.a[4]
            for i in range(self.size):
                result[i] %= MOD
            return Vec(result)
        result = array.array('l', [i + j for i, j in zip(self.a, other.a)])
        result[1] += self.a[2] * other.a[0]
        result[3] += self.a[4] * other.a[0]
        result[3] += self.a[5] * other.a[1]
        result[4] += self.a[5] * other.a[2]
        result[6] += self.a[7] * other.a[0]
        result[6] += self.a[8] * other.a[1]
        result[6] += self.a[9] * other.a[3]
        result[7] += self.a[8] * other.a[2]
        result[7] += self.a[9] * other.a[4]
        result[8] += self.a[9] * other.a[5]
        result[10] += self.a[11] * other.a[0]
        result[10] += self.a[12] * other.a[1]
        result[10] += self.a[13] * other.a[3]
        result[10] += self.a[14] * other.a[6]
        result[11] += self.a[12] * other.a[2]
        result[11] += self.a[13] * other.a[4]
        result[11] += self.a[14] * other.a[7]
        result[12] += self.a[13] * other.a[5]
        result[12] += self.a[14] * other.a[8]
        result[13] += self.a[14] * other.a[9]
        for idx, _ in enumerate(result):
            result[idx] %= MOD
        return Matrix(result)

node = [
    Matrix(array.array('l', [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1])),
    Matrix(array.array('l', [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1])),
]

identity = Matrix(None)


n, q = map(int, input().split())
s = input().strip()
s_seq = [int(x) for x in s]
st = SegmentTree(n, identity)
st.build([node[x] for x in s_seq])
for _ in range(q):
    t, *args = map(int, input().split())
    if t == 1:
        i = args[0] - 1
        s_seq[i] = 1 - s_seq[i]
        st.update(i, node[s_seq[i]])
    else:
        l, r = args
        ans = st.query(l - 1, r, Vec(array.array('l', [0, 0, 0, 0, 0, 1])), Vec(array.array('l', [1, 0, 0, 0, 0, 0])))
        print(ans)
0