P11657 「FAOI-R5」datealive

 

给定长度为 $n$ 的序列 $c_1,c_2,\cdots,c_n$，$c_i\in\{0,1\}$。序列中每个元素都对应一个括号，若 $c_i=0$ 则该位置上的括号是左括号，若 $c_i=1$ 则该位置上的括号是右括号。 我们用 $f(l,r)$ 表示区间 $[l,r]$ 内的括号序列是否合法。若 $c_l,c_{l+1},\cdots,c_r$ 组成的括号序列合法则为 $f(l,r)=1$，否则则为 $f(l,r)=0$。 合法括号序列的定义： - 空串是合法括号序列； - 若 `A` 是合法括号序列，`(A)` 是合法括号序列； - 若 `A` 和 `B` 是合法括号序列，`AB` 是合法括号序列。 你需要**在线地**执行 $q$ 次操作，分为两种： - `1 l r`，查询 $\max\limits_{[l',r']\in[l,r]}\{(r'-l'+1)\cdot f(l',r')\}$，即查询 $[l,r]$ 间的最长合法括号子串的长度。 - `2 l r`，对于 $i\in[l,r]$，将 $c_i$ 修改为 $(1-c_i)$，即将 $[l,r]$ 间的括号逐个调转方向。

无

无

### 样例 1 解释 解密后的结果如下： ``` 10 10 0 1 1 0 0 1 0 0 1 1 2 8 9 2 1 6 2 2 6 2 7 8 2 2 8 2 5 6 2 4 5 1 3 6 1 6 9 1 10 10 ``` $7$ 次修改后的括号串为 $)((())()()$。 - 对于第一组询问，截取子串 $[3,6]$ 得 $(())$。整个子串是合法的括号序列，故答案为 $6-3+1=4$。 - 对于第二组询问，截取子串 $[6,9]$ 得 $)()($。子串 $[7,8]$ 是其中最长的合法括号子串，故答案为 $8-7+1=2$。 - 对于第三组询问，截取子串 $[10,10]$ 得 $)$。该子串中合法括号子串为空串，故答案为 $0$。 ### 数据规模与约定 **本题采用捆绑测试。** | Subtask 编号 | $n \le$ | $q \le$ | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $100$ | $10$ | × | | $2$ | $2 \times 10^4$ | $2 \times 10^4$ | $10$ | × | | $3$ | $4 \times 10^6$ | $10^5$ | $20$ | $\checkmark$ | | $4$ | $10^5$ | $10^5$ | $30$ | × | | $5$ | $4 \times 10^6$ | $10^5$ | $30$ | × | 特殊性质：保证没有修改操作。 对于所有数据，$1 \le n\le 4 \times 10^6$，$1\le q \le 10^{5}$，$1 \le l',r' \le n$，$op\in\{1,2\}$，$c_i\in\{0,1\}$。 本题除 Subtask #3 外保证操作类型随机生成，即每次选择一个 $\{1,2\}$ 中的随机数（选到 $1$ 和 $2$ 的概率均为 $50\%$）作为 $op$。 本题题目附件附有大样例。