結果
問題 |
No.1802 Range Score Query for Bracket Sequence
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()