「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]$ 间的括号逐个调转方向。
输入输出格式
输入格式
第一行两个正整数 $n,q$，分别代表序列长度和操作次数。
接下来 $n$ 个非负整数 $c_1,c_2\cdots,c_n$，代表初始序列。
接下来 $q$ 行，每行三个正整数 $op,l',r'$，表示操作类型和加密后的 $l,r$。
为了强制在线，数据经过加密，我们通过如下过程解密：记 $p$ 为上次查询操作的答案，没有则为 $0$。$l=((l'+p)\bmod n)+1,r=((r'+p)\bmod n)+1$，若 $l>r$ 则交换 $l,r$。
$op,l,r$ 表示操作的三个参数，若 $op=1$ 表示题面中的 `1 l r` 操作；若 $op=2$ 表示题面中的 `2 l r` 操作。
输出格式
对于每次查询，输出一行一个非负整数表示查询的答案。
输入输出样例
输入样例 #1
10 10
0 1 1 0 0 1 0 0 1 1
2 7 8
2 10 5
2 5 1
2 7 6
2 7 1
2 4 5
2 3 4
1 5 2
1 4 1
1 7 7输出样例 #1
4
2
0输入样例 #2
20 20
0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1
2 16 7
2 12 10
1 4 5
1 14 7
1 16 7
2 15 12
1 12 2
1 3 4
1 1 10
2 14 3
2 19 1
1 20 9
2 14 16
1 10 13
1 6 8
2 1 2
1 8 16
1 9 15
1 17 12
2 15 14输出样例 #2
0
2
8
2
0
2
6
4
0
2
0
0说明
### 样例 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$。
本题题目附件附有大样例。