結果

問題 No.3208 Parse AND OR Affection
ユーザー amesyu
提出日時 2025-07-22 18:15:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,642 bytes
コンパイル時間 547 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 121,792 KB
最終ジャッジ日時 2025-07-22 18:15:51
合計ジャッジ時間 16,213 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys

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

# --- Global setup for transformation logic ---
# func_id: 0:id, 1:not, 2:const_T, 3:const_F
# COMPOSE[f][g] computes f o g
COMPOSE = [
    [0, 1, 2, 3],  # id o g
    [1, 0, 3, 2],  # not o g
    [2, 2, 2, 2],  # const_T o g
    [3, 3, 3, 3],  # const_F o g
]
# APPLY[f] gives the tuple (f(True), f(False))
APPLY = [(True, False), (False, True), (True, True), (False, False)]

# --- Segment Tree Implementation ---
# Each node stores: (composite_function, count_true_from_T, count_true_from_F)
SEG_TREE = []
H = [] # Transformation sequence
N_PRIME = 0

def merge(left, right):
    """Merges two segment tree nodes."""
    comp_func = COMPOSE[right[0]][left[0]]
    
    # Calculate total true outcomes for a T input
    t_from_t = left[1]
    # Add contribution from the right half, transformed by the left half's result
    if APPLY[left[0]][0]:  # if left_func(T) is True
        t_from_t += right[1]
    else: # if left_func(T) is False
        t_from_t += right[2]

    # Calculate total true outcomes for an F input
    t_from_f = left[2]
    # Add contribution from the right half, transformed by the left half's result
    if APPLY[left[0]][1]:  # if left_func(F) is True
        t_from_f += right[1]
    else: # if left_func(F) is False
        t_from_f += right[2]

    return comp_func, t_from_t, t_from_f

def build_seg_tree(k, l, r):
    """Builds the segment tree recursively."""
    if r - l == 1:
        func = H[l]
        SEG_TREE[k] = (func, 1 if APPLY[func][0] else 0, 1 if APPLY[func][1] else 0)
        return
    
    mid = (l + r) // 2
    build_seg_tree(2 * k + 1, l, mid)
    build_seg_tree(2 * k + 2, mid, r)
    SEG_TREE[k] = merge(SEG_TREE[2 * k + 1], SEG_TREE[2 * k + 2])

def query_seg_tree(a, b, k, l, r):
    """Queries the segment tree for the range [a, b)."""
    if r <= a or b <= l:
        return (0, 0, 0)  # Identity element for merge
    if a <= l and r <= b:
        return SEG_TREE[k]

    mid = (l + r) // 2
    left_res = query_seg_tree(a, b, 2 * k + 1, l, mid)
    right_res = query_seg_tree(a, b, 2 * k + 2, mid, r)
    return merge(left_res, right_res)

def main():
    global N, Q, H, SEG_TREE, N_PRIME
    try:
        N, Q = map(int, readline().split())
        X = readline().strip()
    except (IOError, ValueError):
        return

    N_PRIME = (N + 1) // 2
    A = [(X[2 * i] == 'T') for i in range(N_PRIME)]
    
    op_map = {'+': 0, '*': 1, '^': 2}
    H = [0] * (N_PRIME - 1)
    for i in range(N_PRIME - 1):
        op = op_map[X[2 * i + 1]]
        operand = A[i + 1]
        if op == 0: H[i] = 2 if operand else 0  # OR
        elif op == 1: H[i] = 0 if operand else 3  # AND
        else: H[i] = 1 if operand else 0  # XOR

    # --- DP Precomputation ---
    NUM_T = [0] * N_PRIME
    NUM_F = [0] * N_PRIME
    if A[0]: NUM_T[0] = 1
    else: NUM_F[0] = 1

    for q in range(1, N_PRIME):
        h = H[q - 1]
        t_is_t, f_is_t = APPLY[h][0], APPLY[h][1]
        
        num_t_current = (1 if A[q] else 0)
        num_t_current += NUM_T[q - 1] if t_is_t else 0
        num_t_current += NUM_F[q - 1] if f_is_t else 0
        
        NUM_T[q] = num_t_current
        NUM_F[q] = (q + 1) - num_t_current

    TOTAL_T = [0] * (N_PRIME + 1)
    for i in range(N_PRIME):
        TOTAL_T[i + 1] = TOTAL_T[i] + NUM_T[i]

    # --- Build Segment Tree ---
    SEG_TREE = [(0, 0, 0)] * (4 * (N_PRIME - 1))
    if N_PRIME > 1:
        build_seg_tree(0, 0, N_PRIME - 1)

    # --- Process Queries ---
    for _ in range(Q):
        L, R = map(int, readline().split())
        l_prime, r_prime = (L + 1) // 2, (R + 1) // 2
        
        # Convert to 0-based indices
        l_idx, r_idx = l_prime - 1, r_prime - 1
        
        # Expressions starting and ending in [L', R']
        ans = TOTAL_T[r_prime] - TOTAL_T[l_prime - 1]
        
        # Subtract expressions starting before L' and ending in [L', R']
        if l_idx > 0:
            num_t_before = NUM_T[l_idx - 1]
            num_f_before = l_idx - num_t_before
            
            # Query on transforms h_{L'-1} ... h_{R'-2}
            # This is H array indices [l_idx, r_idx-1]
            if l_idx <= r_idx - 1:
                # Query range is [l_idx, r_idx) in segment tree
                _, t_from_t, t_from_f = query_seg_tree(l_idx, r_idx, 0, 0, N_PRIME - 1)
                correction = num_t_before * t_from_t + num_f_before * t_from_f
                ans -= correction

        print(ans)

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