結果

問題 No.2762 Counting and Deleting
コンテスト
ユーザー magurofly
提出日時 2024-05-09 13:41:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 609 ms / 4,000 ms
コード長 3,496 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 123,592 KB
最終ジャッジ日時 2024-12-16 03:32:06
合計ジャッジ時間 6,904 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def debug(text):
    print("\033[36m" + str(text) + "\033[m", file = sys.stderr)

MOD = 998244353

class BIT:
    def __init__(self, n):
        if type(n) is list:
            self.tree = [0] + n
            n = len(n)
            for v in range(1, n):
                p = v + (-v & v)
                if p <= n:
                    self.tree[p] += self.tree[v]
        else:
            self.tree = [0] * (n + 1)
        self.len = n
        self.depth = n.bit_length()
    
    def sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l)
    
    def prefix_sum(self, r):
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= -r & r
        return s
    
    def add(self, i, x):
        i += 1
        while i <= self.len:
            self.tree[i] += x
            i += -i & i
    
    # min(x for x in range(0, self.len) if self.prefix_sum(x) >= x)
    def lower_bound(self, x):
        if x == 0:
            return 0
        s = 0
        p = 0
        for i in range(self.depth, -1, -1):
            k = p + (1 << i)
            if k <= self.len and s + self.tree[k] < x:
                s += self.tree[k]
                p += 1 << i
        return p + 1

class Segtree:
    def op(self, x, y):
        a, b, c, d, e, f = x
        g, h, i, j, k, l = y
        return (
            (a * g + b * j) % MOD,
            (a * h + b * k) % MOD,
            (a * i + b * l + c) % MOD,
            (d * g + e * j) % MOD,
            (d * h + e * k) % MOD,
            (d * i + e * l + f) % MOD,
        )

    def e(self):
        return (1, 0, 0, 0, 1, 0)

    def __init__(self, a):
        if type(a) is int:
            a = [self.e()] * a
        n = len(a)
        size = 1
        while size < n: size <<= 1
        self.tree = [self.e()] * (size * 2)
        for i, x in enumerate(a):
            self.tree[size + i] = x
        for i in reversed(range(1, size)):
            self.tree[i] = self.op(self.tree[i << 1], self.tree[i << 1 | 1])
        self.size = size

    def __getitem__(self, p):
        return self.tree[self.size + p]

    def __setitem__(self, p, a):
        p += self.size
        self.tree[p] = a
        while p > 1:
            p >>= 1
            self.tree[p] = self.op(self.tree[p << 1], self.tree[p << 1 | 1])

    def fold(self, l, r):
        x = self.e()
        y = self.e()
        l += self.size
        r += self.size
        while l < r:
            if l & 1 != 0:
                x = self.op(x, self.tree[l])
                l += 1
            l >>= 1
            if r & 1 != 0:
                r -= 1
                y = self.op(self.tree[r], y)
            r >>= 1
        return self.op(x, y)

N, Q = map(int, input().split())
S = input()
queries = [list(map(int, input().split())) for _ in range(Q)]

A0 = (1, 1, 0, 0, 1, 0)
A1 = (1, 0, 0, 1, 1, 1)
A_ = (1, 0, 0, 0, 1, 0)

rest = BIT([1] * N)
seg = Segtree([A0 if S[N - 1 - i] == "0" else A1 for i in range(N)])

# debug(rest.tree)

for t, l, r in queries:
    l -= 1
    if t == 1:
        # debug(f"remove [{l}, {r})")
        while l < r:
            lb = rest.lower_bound(rest.prefix_sum(l) + 1)
            # debug(f"  lb={lb}")
            if lb == None or lb > r: break
            i = lb - 1
            seg[N - 1 - i] = A_
            rest.add(i, -1)
            l = lb
            # debug(f"  removed {i}")
    else:
        a, b, c, d, e, f = seg.fold(N - r, N - l)
        # debug((a, b, c, d, e, f))
        print((c + f) % MOD)
0