AT_abc341_e [ABC341E] Alternating String

题目描述

我们称仅由 0 和 1 组成，且字符串中任意连续的 $2$ 个字符都不相同的字符串为好字符串。
给定一个长度为 $N$ 的仅由 0 和 1 组成的字符串 $S$。有 $Q$ 个查询，请依次处理每个查询。
查询有以下两种类型：

• 1 L R ：将 $S$ 的第 $L$ 个字符到第 $R$ 个字符的 0 和 1 反转。即，对于满足 $L\leq i\leq R$ 的整数 $i$，如果 $S$ 的第 $i$ 个字符为 0，则变为 1，如果为 1，则变为 0。
• 2 L R ：取出 $S$ 的第 $L$ 个字符到第 $R$ 个字符（顺序不变）组成一个长度为 $R-L+1$ 的字符串 $S'$。如果 $S'$ 是好字符串，则输出 Yes，否则输出 No。

输入格式

输入按以下格式从标准输入给出。

$N$ $Q$
$S$
$query_1$
$query_2$
$\vdots$
$query_Q$

每个查询 $query_i$ $(1\leq i\leq Q)$ 为以下两种形式之一：

$1$ $L$ $R$

或

$2$ $L$ $R$

输出格式

设第 $2$ 种类型的查询有 $K$ 个，请输出 $K$ 行。
第 $i$ 行输出第 $i$ 个第 $2$ 种类型查询的结果。

输入输出样例 #1

输入 #1

5 6
10100
2 1 3
2 1 5
1 1 4
2 1 5
1 3 3
2 2 4

输出 #1

Yes
No
Yes
No

输入输出样例 #2

输入 #2

1 2
1
1 1 1
2 1 1

输出 #2

Yes

说明/提示

限制条件

• $1\leq N, Q\leq 5\times 10^5$
• $S$ 是长度为 $N$ 的仅由 0 和 1 组成的字符串
• 对于两种类型的查询，$1\leq L\leq R\leq N$
• 至少存在一个第 $2$ 种类型的查询
• $N$、$Q$、$L$、$R$ 均为整数

样例解释 1

初始时，$S=$10100。依次处理每个查询如下：

• 对于第 $1$ 个查询，取出 $S$ 的第 $1$ 到第 $3$ 个字符，得到 $S'=$101。这是好字符串，输出 Yes。
• 对于第 $2$ 个查询，取出 $S$ 的第 $1$ 到第 $5$ 个字符，得到 $S'=$10100。这不是好字符串，输出 No。
• 对于第 $3$ 个查询，将 $S$ 的第 $1$ 到第 $4$ 个字符的 0 和 1 反转。此时 $S=$01010。
• 对于第 $4$ 个查询，取出 $S$ 的第 $1$ 到第 $5$ 个字符，得到 $S'=$01010。这是好字符串，输出 Yes。
• 对于第 $5$ 个查询，将 $S$ 的第 $3$ 个字符的 0 和 1 反转。此时 $S=$01110。
• 对于第 $6$ 个查询，取出 $S$ 的第 $2$ 到第 $4$ 个字符，得到 $S'=$111。这不是好字符串，输出 No。

样例解释 2

注意，仅由 0 或 1 组成的长度为 $1$ 的字符串也满足好字符串的条件。

由 ChatGPT 4.1 翻译