No.3652 Range Bracket Sequence
タグ : / 解いたユーザー数 60
作問者 :
とある理系大学生の日常
Problem Statement
You are given a string $S$ of length $N$ consisting of ( and ).
You are given $Q$ queries. Each query is one of the following $2$ types. Process them in the given order.
1 x t: Change the $x$-th character of the string $S$ to(if $t=1$, or to)if $t=2$.2 l r: Let $T$ be the substring obtained by extracting the $l$-th through $r$-th characters of the string $S$. When the following operation is repeated on the string $T$ until it can no longer be performed, output the maximum possible number of characters that can be deleted.- Among the characters of $T$, choose indices $a, b$ such that $a < b$, $T_a =$
(, and $T_b =$), and delete those $2$ characters. The remaining characters are concatenated, keeping their original order.
(Here, $T_a$ and $T_b$ denote the $a$-th and $b$-th characters of the string $T$, respectively.)
- Among the characters of $T$, choose indices $a, b$ such that $a < b$, $T_a =$
It is guaranteed that in every test case there is at least $1$ query of the form 2 l r.
Constraints
- $1 \le N, Q \le 2 \times 10^5$
- $S$ is a string of length $N$ consisting of
(and) - For query 1, $1 \le x \le N$
- For query 1, $t \in \{1, 2\}$
- For query 2, $1 \le l \le r \le N$
- $N, Q, x, t, l, r$ are all integers
Input
The input is given from Standard Input in the following format.
$N$ $Q$ $S$ $query_1$ $query_2$ $\vdots$ $query_Q$
Each query $query_i$ is in one of the following formats.
1 x t
2 l r
Output
Let $k$ be the number of queries of type $2$. Output $k$ lines.
On the $i$-th line, output the answer to the $i$-th query of type $2$ (the maximum total number of deleted characters).
Print a newline at the end.
Sample
Sample 1
Input
5 3 ()(() 2 1 5 1 3 2 2 2 5
Output
4 2
In the $1$st query, $T =$ ()((). Choosing and deleting the $1$st character ( and the $2$nd character ) gives ((). Next, deleting the $1$st character ( and the $3$rd character ) leaves (, and no more operations can be performed. A total of $4$ characters were deleted, so output 4.
In the $2$nd query, the $3$rd character of $S$ is changed to ), and $S$ becomes ())().
In the $3$rd query, $T =$ ))(). Deleting the $3$rd character ( and the $4$th character ) gives )), for a total of $2$ deleted characters.
Sample 2
Input
4 2 )(() 2 1 4 2 2 3
Output
2 0
In the $1$st query, $T =$ )((). Deleting the $2$nd character ( and the $4$th character ) deletes $2$ characters.
In the $2$nd query, $T =$ ((. No valid pair can be chosen, so output 0.
Sample 3
Input
6 4 ((())) 2 1 6 1 1 2 2 1 6 2 2 5
Output
6 4 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。