AT_abc331_f [ABC331F] Palindrome Query

题目描述

给定一个由小写英文字母组成、长度为 $N$ 的字符串 $S$。
请按给定顺序处理 $Q$ 个如下所述的查询。
查询有以下两种类型之一：

• 1 x c ：将 $S$ 的第 $x$ 个字符修改为小写英文字母 $c$。
• 2 L R ：如果 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的子串是回文串，则输出 Yes，否则输出 No。

输入格式

输入按以下格式从标准输入给出。这里 $\text{query}_i$ 表示第 $i$ 个需要处理的查询。

$N$ $Q$
$S$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个查询有以下两种格式之一：

$1$ $x$ $c$

$2$ $L$ $R$

输出格式

请按照题目要求，对每个查询输出答案，每个答案占一行。

输入输出样例 #1

输入 #1

7 8
abcbacb
2 1 5
2 4 7
2 2 2
1 5 c
2 1 5
2 4 7
1 4 c
2 3 6

输出 #1

Yes
No
Yes
No
Yes
Yes

说明/提示

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 10^5$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串
• $1 \leq x \leq N$
• $c$ 是小写英文字母
• $1 \leq L \leq R \leq N$
• $N, Q, x, L, R$ 均为整数

样例解释 1

初始时，$S =$ abcbacb。
对于第 $1$ 个查询，$S$ 的第 $1$ 到第 $5$ 个字符组成的字符串为 abcba，这是回文串，因此输出 Yes。
对于第 $2$ 个查询，$S$ 的第 $4$ 到第 $7$ 个字符组成的字符串为 bacb，这不是回文串，因此输出 No。
对于第 $3$ 个查询，$S$ 的第 $2$ 到第 $2$ 个字符组成的字符串为 b，这是回文串，因此输出 Yes。
对于第 $4$ 个查询，将 $S$ 的第 $5$ 个字符修改为 c，$S$ 变为 abcbccb。
对于第 $5$ 个查询，$S$ 的第 $1$ 到第 $5$ 个字符组成的字符串为 abcbc，这不是回文串，因此输出 No。
对于第 $6$ 个查询，$S$ 的第 $4$ 到第 $7$ 个字符组成的字符串为 bccb，这是回文串，因此输出 Yes。
对于第 $7$ 个查询，将 $S$ 的第 $4$ 个字符修改为 c，$S$ 变为 abccccb。
对于第 $8$ 个查询，$S$ 的第 $3$ 到第 $6$ 个字符组成的字符串为 cccc，这是回文串，因此输出 Yes。

由 ChatGPT 4.1 翻译