結果
| 問題 |
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 |
ソースコード
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()