AT_abc322_f [ABC322F] Vacation Query

题目描述

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

请依次处理 $Q$ 个查询。
每个查询由三个整数 $(c, L, R)$ 组成，$c$ 的取值决定了查询的类型。

• 当 $c=1$ 时：对于所有满足 $L \leq i \leq R$ 的整数 $i$，如果 $S_i$ 是 1，则将其变为 0；如果 $S_i$ 是 0，则将其变为 1。
• 当 $c=2$ 时：取出 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的字符串 $T$。请输出 $T$ 中连续的 1 的最大长度。

输入格式

输入按以下格式从标准输入读入。这里 $\mathrm{query}_i$ 表示第 $i$ 个查询。

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

每个查询的格式如下：

$c$ $L$ $R$

输出格式

设 $c=2$ 的查询有 $k$ 个，请输出 $k$ 行。
第 $i$ 行输出第 $i$ 个 $c=2$ 查询的答案。

输入输出样例 #1

输入 #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

说明/提示

数据范围

• $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$ 均为整数

样例解释 1

依次处理查询如下：

• 初始时，$S=$ 1101110。
• 第 1 个查询，$T=$ 1101110。$T$ 中连续的 1 最长为第 4 到第 6 个字符的 111，答案为 $3$。
• 第 2 个查询，$T=$ 101。$T$ 中连续的 1 最长为第 1 或第 3 个字符的 1，答案为 $1$。
• 第 3 个查询，操作后 $S$ 变为 1110000。
• 第 4 个查询，$T=$ 00。$T$ 中没有 1，答案为 $0$。
• 第 5 个查询，操作后 $S$ 变为 1111111。
• 第 6 个查询，$T=$ 1111111。$T$ 中连续的 1 最长为第 1 到第 7 个字符的 1111111，答案为 $7$。

由 ChatGPT 4.1 翻译