結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー amesyu
提出日時 2025-07-22 18:21:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,699 bytes
コンパイル時間 479 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 212,904 KB
最終ジャッジ日時 2025-07-22 18:21:53
合計ジャッジ時間 38,630 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Generated By Gemini 2.5 Pro

import sys

# Set recursion limit for deep segment tree and use faster I/O
sys.setrecursionlimit(252525 + 5)
readline = sys.stdin.readline

def mat_mul(A, B):
    """Multiplies two 4x4 matrices."""
    C = [[0, 0, 0, 0] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                C[i][j] += A[i][k] * B[k][j]
    return C

def solve():
    try:
        N, Q = map(int, readline().split())
        X = readline().strip()
    except (IOError, ValueError):
        return

    N_prime = (N + 1) // 2
    
    # --- 1. Preprocessing: Create Transition Matrices ---
    identity_matrix = [[(1 if i == j else 0) for j in range(4)] for i in range(4)]
    matrices = [identity_matrix] * N_prime

    A = [(X[2 * i] == 'T') for i in range(N_prime)]
    op_map = {'+': 0, '*': 1, '^': 2}
    
    for q in range(N_prime): # 0-indexed operand q
        # Default matrix for a new expression starting at q
        c = 1 if A[q] else 0
        f = 1 - c
        # M maps [T_old, F_old, Total_old, 1] to [T_new, F_new, Total_new, 1]
        # Base case: start a new sequence
        # T_new = c, F_new = f, Total_new = c
        M = [[0,0,0,0], [0,0,0,0], [0,0,0,0], [c,f,c,1]]
        
        if q > 0: # If there's a previous state to transform
            op = op_map[X[2 * q - 1]]
            operand = A[q]
            # h(v) = eval(v, op, operand)
            # h(T)=T, h(F)=F -> id
            # h(T)=F, h(F)=T -> not
            # h(T)=T, h(F)=T -> const_T
            # h(T)=F, h(F)=F -> const_F
            if op == 0:   # OR
                h_T_is_T, h_F_is_T = (True, True) if operand else (True, False)
            elif op == 1: # AND
                h_T_is_T, h_F_is_T = (True, False) if operand else (False, False)
            else: # XOR
                h_T_is_T, h_F_is_T = (False, True) if operand else (True, False)
            
            # T_new = T_old*h(T)_is_T + F_old*h(F)_is_T + c
            # F_new = T_old*h(T)_is_F + F_old*h(F)_is_F + f
            # Total_new = Total_old + T_new
            M[0][0] = 1 if h_T_is_T else 0
            M[0][1] = 0 if h_T_is_T else 1
            M[0][2] = 1 if h_T_is_T else 0 # Contribution to Total_new
            M[1][0] = 1 if h_F_is_T else 0
            M[1][1] = 0 if h_F_is_T else 1
            M[1][2] = 1 if h_F_is_T else 0
            M[2][2] = 1 # Total_old persists
            M[3][2] += M[0][2]*0 + M[1][2]*0 # Add c to Total_new
            
        matrices[q] = M
        
    # --- 2. Build Segment Tree ---
    seg_tree = [identity_matrix] * (2 * N_prime)
    
    # Populate leaves
    for i in range(N_prime):
        seg_tree[N_prime + i] = matrices[i]
    
    # Build tree by merging up
    for i in range(N_prime - 1, 0, -1):
        seg_tree[i] = mat_mul(seg_tree[2 * i], seg_tree[2 * i + 1])
        
    # --- 3. Process Queries ---
    for _ in range(Q):
        L, R = map(int, readline().split())
        l_idx, r_idx = (L - 1) // 2, (R - 1) // 2
        
        # Query segment tree for matrix product over [l_idx, r_idx]
        res_matrix = identity_matrix
        l, r = l_idx + N_prime, r_idx + N_prime + 1
        while l < r:
            if l & 1:
                res_matrix = mat_mul(res_matrix, seg_tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_matrix = mat_mul(res_matrix, seg_tree[r])
            l >>= 1
            r >>= 1
            
        # The answer is the (3,2) element (0-indexed) of the product matrix,
        # which corresponds to the final TOTAL_T after starting with [0,0,0,1].
        print(res_matrix[3][2])

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