← 返回题目列表

Codeforces · 1881/G

G. 安雅与神秘的弦

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

Anya收到了从罗马带来的长度为$$$n$$$的字符串$$$s$$$。字符串 $$$s$$$ 由小写拉丁字母组成,乍一看不会引起任何怀疑。字符串上附加了一条指令。

指令开始。

回文是从左到右和从右到左读相同的字符串。例如,字符串“anna”、“aboba”、“level”是回文,而字符串“gorilla”、“banan”、“off”则不是。

字符串 $$$s$$$ 的子字符串 $$$[l \ldots r]$$$ 是字符串 $$$s_l s_{l+1} \ldots s_{r-1} s_r$$$。例如,字符串“ Generation”的子字符串$$$[4 \ldots 6]$$$是字符串“era”。

如果一个字符串不包含长度至少为 2 的回文子串,则该字符串被称为漂亮字符串。例如,字符串“fox”、“abcdef”和“yioy”很漂亮,而字符串“xyxx”、“yikjkitrb”则不然。

当整数 $$$x$$$ 添加到字符 $$$s_i$$$ 时,它会被字母表中的下一个字符替换 $$$x$$$ 次,其中“z”被“a”替换。

当整数 $$$x$$$ 被添加到字符串 $$$s$$$ 的子串 $$$[l, r]$$$ 时,它变成字符串 $$$s_1 s_2 \ldots s_{l-1} (s_l + x) (s_{l+1} + x) \ldots (s_{r-1} + x) (s_r + x) s_{r+1} \ldots s_n$$$。例如,当字符串“abazaba”的子字符串$$$[2, 4]$$$与数字$$$6$$$相加时,得到的字符串为“ahgfaba”。

指令结束。

读完说明后,安雅接受了她必须回答 $$$m$$$ 询问的事实。查询可以有两种类型:

1. 将数字 $$$x$$$ 添加到字符串 $$$s$$$ 的子字符串 $$$[l \ldots r]$$$ 中。
2、判断字符串$$$s$$$的子串$$$[l \ldots r]$$$是否漂亮。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) - 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 字符串 $$$s$$$ 的长度和查询次数。

每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,由小写拉丁字母组成。

接下来的 $$$m$$$ 行包含查询:

- $$$1$$$ $$$l$$$ $$$r$$$ $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^9$$$) - 第一种类型查询的描述;
- $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) - 第二类型查询的描述。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于第二类的每个查询,如果字符串$$$s$$$的子串$$$[l \ldots r]$$$漂亮,则输出“YES”,否则输出“NO”。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

5
12 8
tedubcyyxopz
2 2 5
1 4 8 2
2 1 7
1 3 5 40
1 9 11 3
1 10 10 9
2 4 10
2 10 12
10 4
ubnxwwgzjt
2 4 10
2 10 10
1 6 10 8
2 7 7
11 3
hntcxfxyhtu
1 4 6 1
2 4 10
1 4 10 21
13 2
yxhlmzfhqctir
1 5 9 3
1 8 13 15
2 3
bp
1 1 2 15
1 1 2 18
1 2 2 1000000000

输出 #1

YES
NO
NO
YES
NO
YES
YES
YES

注意

在第一个测试的第一个测试用例中,发生以下情况:

- tedubcyyxopz:字符串 edub 很漂亮;
- tedubcyyxopz $$$\to$$$ tedwdeaaxopz;
- tedwdeaaxopz:字符串 tedwdea 并不美观,因为它包含回文 edwde;
- tedwdeaaxopz $$$\to$$$ terkreaaxopz;
- terkreaaxopz $$$\to$$$ terkreaaarsz;
- terkreaaarsz $$$\to$$$ terkreaaaasz;
- terkreaaaasz:字符串 kreaaaa 并不美观,因为它包含回文 aaaa;
- terkreaaaasz:字符串 asz 很漂亮。