假期查询

题目描述

给定一个长度为 $N$、由 0 和 1 组成的字符串 $S$。设 $S_i$ 表示 $S$ 的第 $i$ 个字符。

按顺序处理 $Q$ 个查询。每个查询由三个整数 $(c, L, R)$ 表示，其中 $c$ 表示查询类型。

• 当 $c=1$：对于满足 $L \le i \le R$ 的每个整数 $i$，若 $S_i$ 为 1 则改为 0，若为 0 则改为 1。
• 当 $c=2$：设 $T$ 为取出 $S$ 的第 $L$ 到第 $R$ 个字符得到的字符串，输出 $T$ 中连续 1 的最大个数。

输入格式

输入按以下格式从标准输入给出，其中 $\mathrm{query}_i$ 表示第 $i$ 个查询：

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询按以下格式给出：

$c$ $L$ $R$

输出格式

设 $k$ 为 $c=2$ 的查询个数。输出 $k$ 行。

第 $i$ 行输出第 $i$ 个 $c=2$ 查询的答案。

样例

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

3
1
0
7

查询按如下方式处理。

初始时，$S=$ 1101110。

对于第一个查询，$T=$ 1101110。$T$ 中最长的连续 1 是从第 4 个字符到第 6 个字符的 111，因此答案为 $3$。

对于第二个查询，$T=$ 101。$T$ 中最长的连续 1 是第 1 个或第 3 个字符处的 1，因此答案为 $1$。

对于第三个查询，该操作将 $S$ 变为 1110000。

对于第四个查询，$T=$ 00。$T$ 中不含 1，因此答案为 $0$。

对于第五个查询，该操作将 $S$ 变为 1111111。

对于第六个查询，$T=$ 1111111。$T$ 中最长的连续 1 是从第 1 个字符到第 7 个字符的 1111111，因此答案为 $7$。

数据范围

• $1 \le N \le 5 \times 10^5$
• $1 \le Q \le 10^5$
• $S$ 是长度为 $N$、由 0 和 1 组成的字符串。
• $c \in \lbrace 1, 2 \rbrace$
• $1 \le L \le R \le N$
• $N$、$Q$、$c$、$L$、$R$ 均为整数。