結果

問題 No.1802 Range Score Query for Bracket Sequence
ユーザー qwewe
提出日時 2025-05-14 13:13:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 6,436 bytes
コンパイル時間 427 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 201,924 KB
最終ジャッジ日時 2025-05-14 13:14:17
合計ジャッジ時間 4,630 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

# Set higher recursion depth for safety, although default is usually sufficient for N=2e5
# sys.setrecursionlimit(200010) 

def solve():
    # Read N and Q
    N, Q = map(int, sys.stdin.readline().split())
    
    # Read the initial string S and convert to a list for mutability
    S_list = list(sys.stdin.readline().strip())

    # Check for edge case N=0. Based on constraints N >= 1, this block might not be strictly necessary.
    # If N could be 0, queries need handling. Assuming N >= 1.
    # if N == 0:
    #    for _ in range(Q):
    #         query_line = sys.stdin.readline().split()
    #         if int(query_line[0]) == 2:
    #              print(0) 
    #    return

    # Initialize segment tree. Size 4*N is a safe upper bound for a binary tree over N leaves.
    # Each node stores a tuple: (count, leftmost_char, rightmost_char)
    # count: number of adjacent "()" pairs within the node's range.
    # leftmost_char: The character at the start index of the node's range.
    # rightmost_char: The character at the end index of the node's range.
    tree = [(0, '', '')] * (4 * N) 

    # Merge function combines results from two children nodes or query subproblems.
    # This logic is key to calculating the count correctly, especially handling pairs crossing the midpoint.
    def merge_results(left_res, right_res):
        # Handle identity cases: if one result represents an empty range, return the other.
        if left_res == (0, '', ''): return right_res
        if right_res == (0, '', ''): return left_res

        # Combine counts from left and right parts.
        new_count = left_res[0] + right_res[0]
        # Check if the boundary characters form an adjacent "()" pair.
        # This uses the rightmost char of the left part and the leftmost char of the right part.
        if left_res[2] == '(' and right_res[1] == ')':
             new_count += 1
        
        # The combined node's boundary characters are the outermost characters of the combined range.
        return (new_count, left_res[1], right_res[2])

    # Build the segment tree recursively from the initial string S_list.
    # Node represents range [start, end] (0-based indices).
    def build(node, start, end):
        if start == end:
            # Leaf node: Represents a single character. Count is 0. Boundary chars are the character itself.
            tree[node] = (0, S_list[start], S_list[start])
        else:
            mid = (start + end) // 2
            # Recursively build left and right children.
            build(2 * node, start, mid)
            build(2 * node + 1, mid + 1, end)
            # Compute this node's value by merging its children's results.
            tree[node] = merge_results(tree[2 * node], tree[2 * node + 1])

    # Update the character at index `idx` to `char`, then update tree bottom-up.
    def update(node, start, end, idx, char):
        if start == end:
             # Reached the leaf node corresponding to index `idx`.
             # Update the character in the underlying list (for consistency/correctness).
             S_list[idx] = char 
             # Update the tree node value. Count is 0, boundary chars are the new char.
             tree[node] = (0, char, char)
             return # Base case reached.

        mid = (start + end) // 2
        # Recurse down to the correct child based on index `idx`.
        if idx <= mid: # idx is in the left child's range [start, mid]
            update(2 * node, start, mid, idx, char)
        else: # idx is in the right child's range [mid + 1, end]
            update(2 * node + 1, mid + 1, end, idx, char)
        
        # After child update, recompute this node's value by merging its children.
        tree[node] = merge_results(tree[2 * node], tree[2 * node + 1])

    # Query the segment tree for the score (count of "()") in the range [l, r].
    def query(node, start, end, l, r):
        # If the node's range [start, end] is completely outside the query range [l, r].
        if r < start or end < l:
            return (0, '', '') # Return identity element, indicates no contribution.
        
        # If the node's range is completely inside the query range.
        if l <= start and end <= r:
            return tree[node] # Return the precomputed value for this node.
        
        # If the node's range partially overlaps the query range.
        mid = (start + end) // 2
        # Recursively query left and right children for the parts overlapping [l, r].
        left_query_res = query(2 * node, start, mid, l, r)
        right_query_res = query(2 * node + 1, mid + 1, end, l, r)
        
        # Combine results from the recursive calls.
        return merge_results(left_query_res, right_query_res)

    # Build the tree initially based on the input string S.
    # Check if N > 0 before building to handle potential empty string case if constraints allowed.
    if N > 0:
        build(1, 0, N - 1) # Use node 1 as root, cover range 0 to N-1.

    # List to store results for type 2 queries.
    results_output = []
    # Process Q queries.
    for _ in range(Q):
        query_line = sys.stdin.readline().split()
        type = int(query_line[0])
        
        if type == 1:
            # Type 1: Update query
            idx = int(query_line[1]) - 1 # Convert 1-based index to 0-based.
            # Determine the new character: '(' becomes ')' and vice versa.
            current_char = S_list[idx]
            new_char = ')' if current_char == '(' else '('
            # Perform the update operation on the segment tree.
            if N > 0: # Ensure index is valid for non-empty string
                 update(1, 0, N - 1, idx, new_char)
        else:
            # Type 2: Score query
            l, r = int(query_line[1]) - 1, int(query_line[2]) - 1 # Convert 1-based indices to 0-based.
            # Perform the query operation on the segment tree for range [l, r].
            if N > 0 and l <= r : # Ensure range is valid and string non-empty
                res = query(1, 0, N - 1, l, r)
                # The score is the count part of the returned tuple.
                results_output.append(str(res[0]))
            else: # Handle invalid range or empty string case
                results_output.append('0')


    # Print all collected results for type 2 queries, separated by newlines.
    print('\n'.join(results_output))

# Execute the main function
solve()
0