結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー amesyu
提出日時 2025-05-28 00:56:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,195 ms / 5,000 ms
コード長 2,209 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 359 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 209,568 KB
最終ジャッジ日時 2025-06-02 00:59:10
合計ジャッジ時間 40,441 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class SegmentTree:
    def __init__(self, arr, op, e):
        self.op = op
        self.e = e
        self.n = len(arr)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.tree = [self.e for _ in range(2 * self.size)]
        for i in range(self.n): self.tree[i + self.size] = arr[i]
        for i in range(self.size - 1, 0, -1): self.update(i)
    def update(self, i):
        self.tree[i] = self.op(self.tree[2 * i + 0], self.tree[2 * i + 1])
    def set(self, i, x):
        i += self.size
        self.tree[i] = x
        i >>= 1
        while i:
            self.update(i)
            i >>= 1
    def get(self, i):
        return self.tree[i + self.size]
    def prod(self, l, r):
        pl = self.e
        pr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                pl = self.op(pl, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                pr = self.op(self.tree[r], pr)
            l >>= 1
            r >>= 1
        return self.op(pl, pr)
    def all_prod(self):
        return self.tree[1]

SIZE = 4

def mul(A, B):
    r = [[0] * SIZE for _ in range(SIZE)]
    for i in range(SIZE):
        for j in range(SIZE):
            for k in range(SIZE):
                r[i][j] += A[i][k] * B[k][j]
    return r

E = [[0] * SIZE for _ in range(SIZE)]
for i in range(SIZE): E[i][i] = 1

N, Q = map(int, input().split())
X = "+" + input()

init = []
for i in range(len(X) // 2):
    
    op, tf = X[2 * i + 0], X[2 * i + 1]
    
    mat = [[0] * SIZE for _ in range(SIZE)]

    if op == "+" and tf == "T":
        mat[0][1] = 1
        mat[1][1] = 1
    elif op == "*" and tf == "F":
        mat[0][0] = 1
        mat[1][0] = 1
    elif op == "^" and tf == "T":
        mat[0][1] = 1
        mat[1][0] = 1
    else:
        mat[0][0] = 1
        mat[1][1] = 1

    if tf == "T": mat[2][1] = 1
    else: mat[2][0] = 1

    mat[2][2] = 1
    mat[1][3] = 1
    mat[3][3] = 1

    init.append(mat)

seg = SegmentTree(init, mul, E)

for _ in range(Q):
    L, R = map(int, input().split())
    result = seg.prod(L // 2, R // 2 + 1)
    print(result[2][1] + result[2][3])
0