結果

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

ソースコード

diff #
raw source code 

# 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 ---
SEG_TREE = []
H = [] # Transformation sequence
N_PRIME = 0

def merge(left, right):
    """Merges two segment tree nodes."""
    if left is None: return right
    if right is None: return left
    
    comp_func = COMPOSE[right[0]][left[0]]
    
    # Calculate total true outcomes for a T input
    t_from_t = left[1]
    if APPLY[left[0]][0]:
        t_from_t += right[1]
    else:
        t_from_t += right[2]

    # Calculate total true outcomes for an F input
    t_from_f = left[2]
    if APPLY[left[0]][1]:
        t_from_f += right[1]
    else:
        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 None  # 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
    if A[0]: NUM_T[0] = 1

    for q in range(1, N_PRIME):
        h = H[q - 1]
        t_is_t, f_is_t = APPLY[h]
        
        num_t_at_prev = NUM_T[q - 1]
        num_f_at_prev = q - num_t_at_prev # Total expressions ending at q-1 is q
        
        num_t_current = (1 if A[q] else 0)
        num_t_current += num_t_at_prev if t_is_t else 0
        num_t_current += num_f_at_prev if f_is_t else 0
        NUM_T[q] = 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 ---
    if N_PRIME > 1:
        SEG_TREE = [(0, 0, 0)] * (4 * (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
        l_idx, r_idx = l_prime - 1, r_prime - 1
        
        ans = TOTAL_T[r_prime] - TOTAL_T[l_prime - 1]
        
        if l_idx > 0:
            num_t_before = NUM_T[l_idx - 1]
            num_f_before = l_idx - num_t_before
            
            # This range corresponds to transforms h_{l_idx} to h_{r_idx-1}
            # The query needs to cover the inclusive range of indices [l_idx, r_idx-1]
            query_start_idx = l_idx
            query_end_idx = r_idx # Use r_idx to make the range [l_idx, r_idx)
            
            if query_start_idx < query_end_idx:
                # --- THIS IS THE CRITICAL FIX ---
                # Query range is inclusive [l_idx, r_idx-1], so query segtree with [l_idx, r_idx)
                res = query_seg_tree(query_start_idx, query_end_idx, 0, 0, N_PRIME - 1)
                if res:
                    _, t_from_t, t_from_f = res
0