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$。