結果

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

ソースコード

diff #
raw source code 

# Generated By Gemini 2.5 Pro

import sys

# 再帰回数の上限と高速化
sys.setrecursionlimit(252525 + 5)
readline = sys.stdin.readline

# --- グローバル変数 ---
N, Q = 0, 0
A = []  # オペランド (True/False)
H = []  # 変換関数 (0:id, 1:not, 2:const_T, 3:const_F)
NUM_T, TOTAL_T = [], []
SEG_TREE = []
N_prime = 0

# --- 変換関数の定義 ---
# 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
]
# f(T), f(F)
APPLY = [(True, False), (False, True), (True, True), (False, False)]

# --- セグメント木の構築とクエリ ---
def merge(left, right):
    comp_func = COMPOSE[right[0]][left[0]]
    
    # Tから始まる式のTrueの個数
    t_from_t = left[1]
    if APPLY[left[0]][0]: # left.comp(T) == T
        t_from_t += right[1]
    else: # left.comp(T) == F
        t_from_t += right[2]

    # Fから始まる式のTrueの個数
    t_from_f = left[2]
    if APPLY[left[0]][1]: # left.comp(F) == T
        t_from_f += right[1]
    else: # left.comp(F) == F
        t_from_f += right[2]

    return comp_func, t_from_t, t_from_f

def build_seg_tree(k, l, r):
    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):
    if r <= a or b <= l:
        return (0, 0, 0) # identity, 0, 0
    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, A, H, NUM_T, TOTAL_T, SEG_TREE, N_prime
    N, Q = map(int, readline().split())
    X = readline().strip()

    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]
        # id, not, const_T, const_F
        if op == 0: H[i] = 2 if operand else 0
        elif op == 1: H[i] = 0 if operand else 3
        else: H[i] = 1 if operand else 0

    NUM_T = [0] * N_prime
    NUM_F = [0] * N_prime
    if A[0]: NUM_T[0] = 1
    else: NUM_F[0] = 1

    for i in range(N_prime - 1):
        h = H[i]
        q = i + 1
        
        t_val, f_val = APPLY[h]
        
        num_t_next = (1 if A[q] else 0)
        if t_val: num_t_next += NUM_T[i]
        if f_val: num_t_next += NUM_F[i]
        NUM_T[q] = num_t_next
        NUM_F[q] = (q + 1) - num_t_next

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

    SEG_TREE = [(0, 0, 0)] * (4 * (N_prime - 1))
    if N_prime > 1:
        build_seg_tree(0, 0, N_prime - 1)

    for _ in range(Q):
        L, R = map(int, readline().split())
        l_prime, r_prime = (L + 1) // 2, (R + 1) // 2
        
        p_prime = l_prime - 1
        
        # 1. L'以降で始まり、R'以前で終わる式の総数
        ans = TOTAL_T[r_prime] - (TOTAL_T[p_prime] if p_prime > 0 else 0)
        
        # 2. L'より前に始まり、[L', R']の範囲で終わる式の数を引く
        if p_prime > 0:
            num_t_at_p = NUM_T[p_prime - 1]
            num_f_at_p = p_prime - num_t_at_p
            
            # 変換 h_{p'} ... h_{r'-1} を求める
            # この合成結果と途中経過の総数をセグ木で求める
            if p_prime <= r_prime -1:
                _, t_from_t, t_from_f = query_seg_tree(p_prime, r_prime, 0, 0, N_prime - 1)
                correction = num_t_at_p * t_from_t + num_f_at_p * t_from_f
                ans -= correction

        print(ans)

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