P17894 [ICPC 2026 Nanchang I] The Meaning of the World
Description
:::epigraph[Tractatus Logico-Philosophicus]
The meaning of the world must lie outside the world
All things in the world are as they are and happen as they happen
There is no value in the world
:::
Fengmi gives you a string $s$ of length $n$, consisting only of “`(`” and “`)`”.
You need to support $q$ operations:
1. Flip the $k$-th bracket, i.e., change “`(`” to “`)`” and “`)`” to “`(`”.
2. Query the length of the longest valid parentheses substring in the interval $[l,r]$.
Formally, you need to compute:
$$f(l,r) = \max (\left\{ j - i + 1 \mid l \le i \le j \le r \land \text{valid}(i,j) \right\}\cup \{0\})$$
where $\text{valid}(i,j)$ indicates that the substring $s[i..j]$ is a valid parentheses sequence.
In this problem, a valid parentheses sequence is defined as follows:
1. The empty sequence is a valid sequence.
2. If $A$ is a valid sequence, then `(`$A$`)` is also a valid sequence.
3. If $A$ and $B$ are both valid sequences, then $AB$ is also a valid sequence.
Input Format
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$) --- the length of the bracket string and the number of operations.
The second line contains a string $s$ of length $n$, consisting only of the characters “`(`” and “`)`”. The given string is not guaranteed to be a valid parentheses sequence.
The next $q$ lines each describe one of the following two operations:
- `1 k` ($1 \le k \le n$): flip the $k$-th bracket.
- `2 l r` ($1 \le l \le r \le n$): query the length of the longest valid parentheses substring in the interval $[l,r]$.
Output Format
For each operation of type $2$, output a single integer on its own line --- the answer.
Explanation/Hint
**Sample 1:**
- Initial string: `()(()())`.
- First query on interval $[1,8]$: the longest valid parentheses substring is `()(()())` (positions $1-8$), length $8$.
- Flip the $4$th bracket: `()())())`.
- Second query on interval $[1,8]$: the longest valid parentheses substring is `()()` (positions $1-4$), length $4$.
- Flip the $7$th bracket: `()())(()`.
- Third query on interval $[1,8]$: the longest valid parentheses substring is `()()` (positions $1-4$), length $4$.
**Sample 2:**
- Initial string: `(()())(()())`.
- First query on interval $[1,12]$: the longest valid parentheses substring is the entire string, length $12$.
- Flip the $3$rd bracket: `(((())(()())`.
- Second query on interval $[1,12]$: the longest valid parentheses substring is `(())(()())` (positions $3-12$), length $10$.
- Flip the $8$th bracket: `(((())())())`.
- Third query on interval $[1,12]$: the longest valid parentheses substring is `(((())())())` (positions $1-12$), length $12$.
- Fourth query on interval $[4,9]$: the longest valid parentheses substring is `()` (positions $4-5$), length $2$.