Flower's Land 2 - المسألة

Little Cyan Fish 和 Big Flower Letter 是两位好朋友。为了庆祝 Flower’s Land 建国 17 周年，Little Cyan Fish 设计了一个新游戏：

游戏使用一个由数字 0、1 和 2 组成的字符串 $s = s_1s_2 \dots s_n$ 进行。
游戏过程如下：
1. 玩家选择一个下标 $i$ ($1 \le i < n$)，使得 $s_i = s_{i+1}$。
  - 值得注意的是，如果不存在这样的 $i$，游戏立即结束。
2. 字符 $s_i$ 和 $s_{i+1}$ 被移除，玩家回到第 1 步。
如果玩家能完全消除字符串（留下空字符串），则赢得游戏。否则，输掉游戏。

为了挑战 Little Cyan Fish，Big Flower Letter 给出了一个长度为 $n$ 的字符串 $s = s_1s_2 \dots s_n$，并提出了以下操作：

1 l r：对于每个 $l \le i \le r$，更新 $s_i \leftarrow (s_i + 1) \pmod 3$。
2 l r：假设 $t = s[l \dots r] = s_l s_{l+1} \dots s_{r-1} s_r$，Little Cyan Fish 需要判断如果使用字符串 $t$ 进行游戏，玩家是否能获胜。

你能帮助 Little Cyan Fish 回答所有询问吗？

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 5 \times 10^5$)，分别表示字符串 $s$ 的长度和询问次数。

下一行包含一个字符串 $s$，表示 Big Flower Letter 给出的字符串。保证 $|s| = n$ 且 $s$ 由数字 0、1 和 2 组成。

接下来的 $q$ 行描述了所有操作，格式如下：

保证 $1 \le l \le r \le n$。

对于每个操作 2，如果玩家能赢得游戏，输出一行包含单词 Yes。否则，输出一行包含单词 No。

Yes
No
Yes
No
Yes

在样例测试中，初始字符串为 $s = 01211012$。

操作 1 是一个询问操作。对于 $s[4 \dots 5] = 11$，我们可以在第一轮选择下标 $i = 1$ 从而赢得游戏。因此，输出 Yes。

操作 2 是一个询问操作。对于 $s[3 \dots 6] = 2110$，无法移除所有字符。因此，输出 No。

操作 3 是一个更新操作。我们需要更新所有 $6 \le i \le 8$ 的 $s_i$。修改后，$s$ 变为 $01211120$。

操作 4 是一个更新操作。我们需要更新所有 $6 \le i \le 8$ 的 $s_i$。修改后，$s$ 变为 $01211201$。

操作 5 是一个询问操作。对于 $s[3 \dots 6] = 2112$，我们可以在第一轮选择下标 $i = 2$。字符串变为 $22$，然后在下一轮选择下标 $i = 1$ 即可赢得游戏。因此，输出 Yes。

操作 6 是一个询问操作。对于 $s[1 \dots 8] = 01211201$，无法移除所有字符。因此，输出 No。

操作 7 是一个更新操作。我们需要更新所有 $1 \le i \le 1$ 的 $s_i$。修改后，$s$ 变为 $11211201$。

操作 8 是一个更新操作。我们需要更新所有 $7 \le i \le 7$ 的 $s_i$。修改后，$s$ 变为 $11211211$。

操作 9 是一个询问操作。对于 $s[1 \dots 8] = 11211211$，可以移除所有字符。因此，输出 Yes。

QOJ.ac