P17894 [ICPC 2026 Nanchang I] The Meaning of the World
题目描述
:::epigraph[《逻辑哲学论》]
世界的意义必定存在于世界之外
世界中的一切事物如其所存在般而存在,如其所发生般而发生
世界之中不存在价值
:::
枫蜜给了你一个长度为 $n$ 的字符串 $s$,仅由 “`(`” 和 “`)`” 组成。
你需要支持 $q$ 次操作:
1. 翻转第 $k$ 个括号,即将 “`(`” 变为 “`)`”,“`)`” 变为 “`(`”;
2. 查询区间 $[l,r]$ 内最长的合法括号子串的长度。
形式化来说,你需要求:
$$f(l,r) = \max (\left\{ j - i + 1 \mid l \le i \le j \le r \land \text{valid}(i,j) \right\}\cup \{0\})$$
其中 $\text{valid}(i,j)$ 表示子串 $s[i..j]$ 是一个合法的括号序列。
在本题中,认为以下的括号序列是合法的:
1. 空序列是一个合法序列。
2. 如果 $A$ 是一个合法序列,则 `(`$A$`)` 也是一个合法序列。
3. 如果 $A$ 和 $B$ 都是合法序列,则 $AB$ 也是一个合法序列。
输入格式
第一行包含两个正整数 $n$ 和 $q$ ($1 \le n, q \le 2 \times 10^5$),表示给定括号串的长度和操作次数。
第二行包含一个长度为 $n$ 的字符串 $s$,仅由 “`(`” 和 “`)`” 组成。不保证给定的字符串是一个合法的括号序列。
接下来 $q$ 行,每行为以下两种操作之一:
- `1 k` ($1 \le k \le n$):翻转第 $k$ 个括号。
- `2 l r` ($1 \le l \le r \le n$):查询区间 $[l,r]$ 内最长的合法括号子串的长度。
输出格式
对于每个操作 $2$,输出一个整数,表示答案。
说明/提示
**样例 1:**
- 初始字符串:`()(()())`;
- 第一次查询区间 $[1,8]$,最长合法括号子串是 `()(()())`(位置 $1-8$),长度为 $8$;
- 翻转第 $4$ 个括号:`()())())`;
- 第二次查询区间 $[1,8]$,最长合法括号子串是 `()()`(位置 $1-4$),长度为 $4$;
- 翻转第 $7$ 个括号:`()())(()`;
- 第三次查询区间 $[1,8]$,最长合法括号子串是 `()()`(位置 $1-4$),长度为 $4$。
**样例 2:**
- 初始字符串:`(()())(()())`;
- 第一次查询区间 $[1,12]$,最长合法括号子串是整个字符串,长度为 $12$;
- 翻转第 $3$ 个括号:`(((())(()())`;
- 第二次查询区间 $[1,12]$,最长合法括号子串是 `(())(()())`(位置 $3-12$),长度为 $10$;
- 翻转第 $8$ 个括号:`(((())())())`;
- 第三次查询区间 $[1,12]$,最长合法括号子串是 `(((())())())`(位置 $1-12$),长度为 $12$;
- 第四次查询区间 $[4,9]$,最长合法括号子串是 `()`(位置 $4-5$),长度为 $2$。