← 返回题目列表

AtCoder · abc341_e

H. 交替字符串

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

由以下内容组成的字符串 0 和 1 被称为 好字符串 如果字符串中的两个连续字符始终不同。 将给出
给你一个字符串 S 长度 N 组成 0 和 1. Q 查询,并且必须按顺序处理。
有两种类型的查询:

  • 1 L R:翻转每个 L-th 至 R第一个字符 S。也就是说,对于每个整数 i 满意 L\leq i\leq R,更改 i- 第一个字符 S to 0 如果是 1,反之亦然。
  • 2 L R:让 S' 是长度的字符串 (R-L+1) 通过提取获得 L-th 至 R第一个字符 S (不改变顺序)。打印 Yes if 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 满足成为好字符串的条件。