← 返回题目列表

AtCoder · abc322_f

I. 假期查询

中文机器翻译题面 查看原题

分数: 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 is 111 来自 4- 第一个字符 6- 第一个字符,所以答案是 3.
  • 对于第二个查询, T = 101。最长的连续序列 1中 T is 1 在 1-st 或 3-rd 字符,所以答案是 1.
  • 对于第三个查询,操作发生变化 S to 1110000.
  • 对于第四个查询, T = 00. T 不包含 1,所以答案是 0.
  • 对于第五个查询,操作发生变化 S to 1111111.
  • 对于第六个查询, T = 1111111。最长的连续序列 1中 T is 1111111 来自 1-st 到 7个字符,所以答案是 7.