分数: 450 点
问题陈述
由以下内容组成的字符串 0 和 1 被称为 好字符串 如果字符串中的两个连续字符始终不同。
将给出
给你一个字符串 S 长度 N 组成 0 和 1.
Q 查询,并且必须按顺序处理。
有两种类型的查询:
1 L R:翻转每个 L-th 至 R第一个字符 S。也就是说,对于每个整数 i 满意 L\leq i\leq R,更改 i- 第一个字符 S to0如果是1,反之亦然。2 L R:让 S' 是长度的字符串 (R-L+1) 通过提取获得 L-th 至 R第一个字符 S (不改变顺序)。打印Yesif S' 是一个很好的字符串并且No否则。
约束
- 1\leq N, Q\leq 5\times 10^5
- S 是一个长度为 N 组成
0和1. - 1\leq L\leq R\leq N 用于类型查询 1 和 2.
- 至少有一个类型为 每个测试用例中的 2.
- N, Q, L,和 R 是整数。
输入
输入由标准输入按以下格式给出:
N Q S query_1 query_2 \vdots query_Q
每个查询 query_i (1\leq i\leq Q) 以以下形式给出:
1 L R
或:
2 L R
输出
让 K 是该类型的查询数 2。打印 K 行。
的 i- 第行应包含对 i类型的第一个查询 2.
示例输入 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
最初, S=10100。当按照给出的顺序处理查询时,会发生以下情况:
- 对于第一个查询,提取得到的字符串 1-st 到 3-rd 字符 S is S'=
101。这是一个很好的字符串,所以打印Yes. - 对于第二个查询,提取得到的字符串 1-st 到 5第一个字符 S is S'=
10100。这不是一个好的字符串,所以打印No. - 对于第三个查询,翻转每个 1-st 到 4第一个字符 S。字符串 S 变为 S=
01010. - 对于第四个查询,提取得到的字符串 1-st 到 5- 第一个字符 S is S'=
01010。这是一个很好的字符串,所以打印Yes. - 对于第五个查询,翻转 3-rd 字符 S。字符串 S 变为 S=
01110. - 对于第六个查询,提取得到的字符串 2-nd 至 4- 第一个字符 S is S'=
111。这不是一个好的字符串,所以打印No.
示例输入 2
1 2 1 1 1 1 2 1 1
示例输出 2
Yes
注意单个字符的字符串 0 or 1 满足成为好字符串的条件。