CF1881G Anya and the Mysterious String

Anya 收到了一串来自罗马的字符串 $s$，长度为 $n$。字符串 $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" 不是美丽字符串。 当给字符 $s_i$ 加上整数 $x$ 时，它会在字母表中向后移动 $x$ 次，"z" 之后回到 "a"。 当给字符串 $s$ 的子串 $[l, r]$ 加上整数 $x$ 时，字符串变为 $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"。 说明书结束。 读完说明书后，Anya 发现她需要回答 $m$ 个询问。询问有两种类型： 1. 给字符串 $s$ 的子串 $[l \ldots r]$ 加上整数 $x$。 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" 都被认为是肯定答案）。

在第一个测试用例的第一个测试中，过程如下： - tedubcyyxopz：字符串 edub 是美丽字符串； - tedubcyyxopz $\to$ tedwdeaaxopz； - tedwdeaaxopz：字符串 tedwdea 不是美丽字符串，因为包含回文串 edwde； - tedwdeaaxopz $\to$ terkreaaxopz； - terkreaaxopz $\to$ terkreaaarsz； - terkreaaarsz $\to$ terkreaaaasz； - terkreaaaasz：字符串 kreaaaa 不是美丽字符串，因为包含回文串 aaaa； - terkreaaaasz：字符串 asz 是美丽字符串。 由 ChatGPT 4.1 翻译