103225: [Atcoder]ABC322 F - Vacation Query

Problem Statement

You are given a string $S$ of length $N$ consisting of 0 and 1. Let $S_i$ denote the $i$-th character of $S$.

Process $Q$ queries in the order they are given.
Each query is represented by a tuple of three integers $(c, L, R)$, where $c$ represents the type of the query.

• When $c=1$: For each integer $i$ such that $L \leq i \leq R$, if $S_i$ is 1, change it to 0; if it is 0, change it to 1.
• When $c=2$: Let $T$ be the string obtained by extracting the $L$-th through $R$-th characters of $S$. Print the maximum number of consecutive 1s in $T$.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 10^5$
• $S$ is a string of length $N$ consisting of 0 and 1.
• $c \in \lbrace 1, 2 \rbrace$
• $1 \leq L \leq R \leq N$
• $N$, $Q$, $c$, $L$, and $R$ are all integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{query}_i$ represents the $i$-th query:

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

Each query is given in the following format:

$c$ $L$ $R$

Output

Let $k$ be the number of queries with $c=2$. Print $k$ lines.
The $i$-th line should contain the answer to the $i$-th query with $c=2$.

Sample Input 1

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

Sample Output 1

3
1
0
7

The queries are processed as follows.

• Initially, $S=$ 1101110.
• For the first query, $T =$ 1101110. The longest sequence of consecutive 1s in $T$ is 111 from the $4$-th character to $6$-th character, so the answer is $3$.
• For the second query, $T =$ 101. The longest sequence of consecutive 1s in $T$ is 1 at the $1$-st or $3$-rd character, so the answer is $1$.
• For the third query, the operation changes $S$ to 1110000.
• For the fourth query, $T =$ 00. $T$ does not contain 1, so the answer is $0$.
• For the fifth query, the operation changes $S$ to 111111.
• For the sixth query, $T =$ 1111111. The longest sequence of consecutive 1s in $T$ is 1111111 from the $1$-st to $7$-th characters, so the answer is $7$.

问题描述

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

按照给定的顺序处理$Q$个查询。
每个查询由一个包含三个整数的元组$(c, L, R)$表示，其中$c$表示查询的类型。

• 当$c=1$时：对于满足$L \leq i \leq R$的每个整数$i$，如果$S_i$为1，将其更改为0；如果它为0，将其更改为1。
• 当$c=2$时：设$T$为通过提取$S$的第$L$个到第$R$个字符得到的字符串。输出$T$中连续的1的最大数量。

限制条件

• $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。在$T$中，从第$4$个字符到第$6$个字符的最长连续1序列是111，所以答案是$3$。
• 对于第二个查询，$T =$ 101。在$T$中，第$1$个或第$3$个字符的最长连续1序列是1，所以答案是$1$。
• 对于第三个查询，操作将$S$更改为1110000。
• 对于第四个查询，$T =$ 00。$T$中不包含1，所以答案是$0$。
• 对于第五个查询，操作将$S$更改为1111111。
• 对于第六个查询，$T =$ 1111111。在$T$中，从第$1$个字符到第$7$个字符的最长连续1序列是1111111，所以答案是$7$。