310754: CF1881G. Anya and the Mysterious String
Description
Anya received a string $s$ of length $n$ brought from Rome. The string $s$ consists of lowercase Latin letters and at first glance does not raise any suspicions. An instruction was attached to the string.
Start of the instruction.
A palindrome is a string that reads the same from left to right and right to left. For example, the strings "anna", "aboba", "level" are palindromes, while the strings "gorilla", "banan", "off" are not.
A substring $[l \ldots r]$ of string $s$ is a string $s_l s_{l+1} \ldots s_{r-1} s_r$. For example, the substring $[4 \ldots 6]$ of the string "generation" is the string "era".
A string is called beautiful if it does not contain a substring of length at least two that is a palindrome. For example, the strings "fox", "abcdef", and "yioy" are beautiful, while the strings "xyxx", "yikjkitrb" are not.
When an integer $x$ is added to the character $s_i$, it is replaced $x$ times with the next character in the alphabet, with "z" being replaced by "a".
When an integer $x$ is added to the substring $[l, r]$ of string $s$, it becomes the string $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$. For example, when the substring $[2, 4]$ of the string "abazaba" is added with the number $6$, the resulting string is "ahgfaba".
End of the instruction.
After reading the instruction, Anya resigned herself to the fact that she has to answer $m$ queries. The queries can be of two types:
- Add the number $x$ to the substring $[l \ldots r]$ of string $s$.
- Determine whether the substring $[l \ldots r]$ of string $s$ is beautiful.
The first line contains an integer $t$ ($1 \le t \le 10^4$) - the number of test cases.
The descriptions of the test cases follow.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) - the length of the string $s$ and the number of queries.
The second line of each test case contains the string $s$ of length $n$, consisting of lowercase Latin letters.
The next $m$ lines contain the queries:
- $1$ $l$ $r$ $x$ ($1 \le l \le r \le n$, $1 \le x \le 10^9$) - description of a query of the first type;
- $2$ $l$ $r$ ($1 \le l \le r \le n$) - description of a query of the second type.
It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.
OutputFor each query of the second type, output "YES" if the substring $[l \ldots r]$ of string $s$ is beautiful, otherwise output "NO".
You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers).
ExampleInput5 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 1000000000Output
YES NO NO YES NO YES YES YESNote
In the first test case of the first test, the following happens:
- tedubcyyxopz: the string edub is beautiful;
- tedubcyyxopz $\to$ tedwdeaaxopz;
- tedwdeaaxopz: the string tedwdea is not beautiful as it contains the palindrome edwde;
- tedwdeaaxopz $\to$ terkreaaxopz;
- terkreaaxopz $\to$ terkreaaarsz;
- terkreaaarsz $\to$ terkreaaaasz;
- terkreaaaasz: the string kreaaaa is not beautiful as it contains the palindrome aaaa;
- terkreaaaasz: the string asz is beautiful.
Output
阿尼亚收到了一条来自罗马的字符串`s`,该字符串由小写拉丁字母组成,看起来并无异常。字符串附带了一份指令。
- 回文串:一个从左到右和从右到左读取都相同的字符串。
- 子串:字符串`s`中从第`l`个到第`r`个字符组成的字符串。
- 美丽字符串:不包含长度至少为2的回文子串的字符串。
- 字符串操作:将整数`x`加到`s`的子串`[l, r]`上,即将该子串中的每个字符在字母表中后移`x`位,`z`后面跟`a`。
阿尼亚需要回答`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:`1 l r x`($1 \le l \le r \le n$, $1 \le x \le 10^9$),描述第一种类型的查询。
- 类型2:`2 l r`($1 \le l \le r \le n$),描述第二种类型的查询。
- 保证所有测试用例的$n$和$m$之和不超过$2 \cdot 10^5$。
**输出:**
- 对于每个第二种类型的查询,如果字符串`s`的子串`[l \ldots r]`是美丽字符串,则输出`"YES"`,否则输出`"NO"`。
- `YES`和`NO`的大小写不敏感。**题目大意:** 阿尼亚收到了一条来自罗马的字符串`s`,该字符串由小写拉丁字母组成,看起来并无异常。字符串附带了一份指令。 - 回文串:一个从左到右和从右到左读取都相同的字符串。 - 子串:字符串`s`中从第`l`个到第`r`个字符组成的字符串。 - 美丽字符串:不包含长度至少为2的回文子串的字符串。 - 字符串操作:将整数`x`加到`s`的子串`[l, r]`上,即将该子串中的每个字符在字母表中后移`x`位,`z`后面跟`a`。 阿尼亚需要回答`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:`1 l r x`($1 \le l \le r \le n$, $1 \le x \le 10^9$),描述第一种类型的查询。 - 类型2:`2 l r`($1 \le l \le r \le n$),描述第二种类型的查询。 - 保证所有测试用例的$n$和$m$之和不超过$2 \cdot 10^5$。 **输出:** - 对于每个第二种类型的查询,如果字符串`s`的子串`[l \ldots r]`是美丽字符串,则输出`"YES"`,否则输出`"NO"`。 - `YES`和`NO`的大小写不敏感。