問題一覧 > 通常問題

No.3652 Range Bracket Sequence

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 60
作問者 : Rino-program / テスター : gomaazarasi 👑 p-adic とある理系大学生の日常
お気に入りにしたユーザー ProblemId : 13694 / 自分の提出
問題文最終更新日: 2026-08-22 13:33:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 511 (Div.2) (順位表) の他の問題:

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.)

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もしくは右上の雲マークをクリックしてアカウントを作成してください。