結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー amesyu
提出日時 2025-06-11 01:53:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,283 ms / 5,000 ms
コード長 2,279 bytes
コンパイル時間 788 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 134,004 KB
最終ジャッジ日時 2025-06-11 01:54:07
合計ジャッジ時間 29,853 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
SIZE2 = SIZE * SIZE

def mul(a, b):
    r = [0] * SIZE2
    for i in range(SIZE):
        for k in range(SIZE):
            for j in range(SIZE):
                r[i*SIZE+j]+=a[i*SIZE+k]*b[k*SIZE+j];
    return r

def pos(i, j):
    return i * SIZE + j

E = [0] * SIZE2
for i in range(SIZE): E[i*SIZE+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] * SIZE2

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

    if tf == "T": mat[pos(2,1)] = 1
    else: mat[pos(2,0)] = 1
    
    mat[pos(2,2)] = 1
    mat[pos(1,3)] = 1
    mat[pos(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[pos(2,1)] + result[pos(2,3)])
0