交替字符串

题目描述

由 0 和 1 组成的字符串中，如果任意两个相邻的字符都不同，则称为好字符串。

给定一个由 0 和 1 组成、长度为 $N$ 的字符串 $S$。 接下来有 $Q$ 个查询，需要按顺序处理。

查询有两种类型：

• 1 L R：将 $S$ 的第 $L$ 到第 $R$ 个字符全部翻转。即对满足 $L \le i \le R$ 的每个整数 $i$，若 $S$ 的第 $i$ 个字符是 1 则改为 0，反之亦然。
• 2 L R：令 $S'$ 为提取 $S$ 的第 $L$ 到第 $R$ 个字符（保持顺序）得到的长度为 $(R-L+1)$ 的字符串。若 $S'$ 是好字符串则输出 Yes，否则输出 No。

输入格式

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

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

每个查询 $query_i$ $(1 \le i \le Q)$ 以下列两种形式之一给出：

$1$ $L$ $R$

或：

$2$ $L$ $R$

输出格式

设 $K$ 为类型 2 的查询数量。输出 $K$ 行。

第 $i$ 行应输出对第 $i$ 个类型 2 查询的应答。

样例

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

Yes
No
Yes
No

初始时，$S=10100$。按给定顺序处理查询时，过程如下：

• 第一个查询，提取 $S$ 的第 1 到第 3 个字符得到的字符串 $S'=101$。这是好字符串，所以输出 Yes。
• 第二个查询，提取 $S$ 的第 1 到第 5 个字符得到的字符串 $S'=10100$。这不是好字符串，所以输出 No。
• 第三个查询，将 $S$ 的第 1 到第 4 个字符全部翻转。字符串 $S$ 变为 $S=01010$。
• 第四个查询，提取 $S$ 的第 1 到第 5 个字符得到的字符串 $S'=01010$。这是好字符串，所以输出 Yes。
• 第五个查询，翻转 $S$ 的第 3 个字符。字符串 $S$ 变为 $S=01110$。
• 第六个查询，提取 $S$ 的第 2 到第 4 个字符得到的字符串 $S'=111$。这不是好字符串，所以输出 No。

1 2
1
1 1 1
2 1 1

Yes

注意，由单个字符 0 或 1 组成的字符串也满足好字符串的条件。

数据范围

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