結果

問題 No.2611 Count 01
コンテスト
ユーザー LyricalMaestro
提出日時 2024-09-14 05:54:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,034 ms / 6,000 ms
コード長 5,141 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 186,888 KB
最終ジャッジ日時 2024-09-14 05:55:19
合計ジャッジ時間 42,289 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2611

from collections import deque

MOD = 998244353

def op(array, left, right):
    # 長さと個数の計算
    for i in (7, 8, 9):
        array[i] = left[i] + right[i]

    new_l10 = (left[7] * right[9]) % MOD
    new_l10 += (left[3] + right[3])
    new_l10 %= MOD    
    array[3] = new_l10

    new_l11 = (left[8] * right[9]) % MOD
    new_l11 += (left[4] + right[4])
    new_l11 %= MOD    
    array[4] = new_l11

    new_r10 = (right[7] * left[9]) % MOD
    new_r10 += (left[5] + right[5])
    new_r10 %= MOD    
    array[5] = new_r10

    new_r10 = (right[8] * left[9]) % MOD
    new_r10 += (left[6] + right[6])
    new_r10 %= MOD    
    array[6] = new_r10

    l1 = (left[7] * left[8]) % MOD
    l1 *= right[9]
    l1 %= MOD
    l2 = (left[8] * right[3]) % MOD
    l3 = (left[7] * right[4]) % MOD
    new_l = (left[1] + right[1]) % MOD
    new_l += l1
    new_l %= MOD
    new_l += l2
    new_l %= MOD
    new_l += l3
    new_l %= MOD
    array[1] = new_l

    r1 = (right[7] * right[8]) % MOD
    r1 *= left[9]
    r1 %= MOD
    r2 = (right[8] * left[5]) % MOD        
    r3 = (right[7] * left[6]) % MOD  
    new_r = (right[2] + left[2]) % MOD
    new_r += r1
    new_r %= MOD      
    new_r += r2
    new_r %= MOD      
    new_r += r3
    new_r %= MOD      
    array[2] = new_r

    ans1 = (right[9] * left[2]) % MOD
    ans2 = (left[9] * right[1]) % MOD
    ans3 = (right[3] * left[6]) % MOD
    ans4 = (right[4] * left[5]) % MOD
    answer = (left[0] + right[0]) % MOD
    answer += ans1
    answer %= MOD
    answer += ans2
    answer %= MOD
    answer += ans3
    answer %= MOD
    answer += ans4
    answer %= MOD
    array[0] = answer






class SegmentTree:
    """
    非再帰版セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        # 0: 区間におけるg(x)の値
        # 1: 区間における「左だけ端を共有する区間」だけに限定したg(x)の値
        # 2: 区間における「右だけ端を共有する区間」だけに限定したg(x)の値
        # 3: 区間における「左だけ端を共有する区間」だけに限定した 「0の個数」の累積和
        # 4: 区間における「左だけ端を共有する区間」だけに限定した 「1の個数」の累積和
        # 5: 区間における「右だけ端を共有する区間」だけに限定した 「0の個数」の累積和
        # 6: 区間における「右だけ端を共有する区間」だけに限定した 「1の個数」の累積和
        # 7: 区間における0の個数
        # 8: 区間における0の個数
        # 9: 有効な区間の長さ
        self.array = [[0] * 10 for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i][3 + a] = 1
            self.array[self.size + i][5 + a] = 1
            self.array[self.size + i][7 + a] = 1
            self.array[self.size + i][9] = 1
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                op(self.array[i], self.array[2 * i], self.array[2 * i + 1])
            end_index = start_index
            start_index = end_index // 2

    def swap(self, ar, i, j):
        tmp = ar[i]
        ar[i] = ar[j]
        ar[j] = tmp

    def shift(self, x):
        index = self.size + x

        ar = self.array[index]
        self.swap(ar, 3, 4)
        self.swap(ar, 5, 6)
        self.swap(ar, 7, 8)
        while index > 1:
            index //= 2
            op(self.array[index], self.array[2 * index], self.array[2 * index + 1])

    def get_max(self, l, r):
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        queue_r = deque()
        queue_l = deque()
        while L < R:
            if R & 1:
                R -= 1
                queue_r.appendleft(self.array[R])
            if L & 1:
                queue_l.append(self.array[L])
                L += 1
            L >>= 1; R >>= 1
        s = [0] * 10
        new_s = [0] * 10
        while len(queue_l) > 0:
            a = queue_l.popleft()
            op(new_s, s, a)
            for i in range(10):
                s[i] = new_s[i]
        while len(queue_r) > 0:
            a = queue_r.popleft()
            op(new_s, s, a)
            for i in range(10):
                s[i] = new_s[i]
        return s[0]


def main():
    N, Q = map(int, input().split())
    S = input()
    queries = []
    for _ in range(Q):
        values = tuple(map(int, input().split()))
        queries.append(values)

    seg_tree = SegmentTree([int(s) for s in S])
    for values in queries:
        if values[0] == 1:
            _, i = values
            seg_tree.shift(i - 1)
        else:
            _, l, r = values
            ans = seg_tree.get_max(l - 1, r)
            print(ans)


if __name__ == "__main__":
    main()
0