分数: 550 点
问题陈述
给你一个字符串 S 长度 N 组成 0 和 1。让 S_i 表示 i- 第一个字符 S.
流程 Q 按给出的顺序进行查询。
每个查询由三个整数的元组表示 (c, L, R),其中 c 表示查询的类型。
- 当 c=1:对于每个整数 i 这样 L \leq i \leq R,如果 S_i is
1,将其更改为0;如果是的话0,将其更改为1. - 当 c=2:让 T 是通过提取得到的字符串 L-th 通过 R- 第一个字符 S。打印最大连续数
1中 T.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 10^5
- S 是一个长度为的字符串 N 组成
0和1. - c \in \lbrace 1, 2 \rbrace
- 1 \leq L \leq R \leq N
- N, Q, c, L,和 R 均为整数。
输入
输入由标准输入按以下格式给出,其中 \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.
样本输入 1
7 6 1101110 2 1 7 2 2 4 1 3 6 2 5 6 1 4 7 2 1 7
示例输出 1
3 1 0 7
查询处理如下。
- 最初,
黑板上写着 S=
1101110. - 对于第一个查询, T =
1101110。最长的连续序列1中 T is111来自 4- 第一个字符 6- 第一个字符,所以答案是 3. - 对于第二个查询, T =
101。最长的连续序列1中 T is1在 1-st 或 3-rd 字符,所以答案是 1. - 对于第三个查询,操作发生变化 S to
1110000. - 对于第四个查询, T =
00. T 不包含1,所以答案是 0. - 对于第五个查询,操作发生变化 S to
1111111. - 对于第六个查询, T =
1111111。最长的连续序列1中 T is1111111来自 1-st 到 7个字符,所以答案是 7.