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$

输出格式

按照题目描述的要求输出查询的答案，每个答案占一行。

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

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$ 都是整数。最初，$S =$ $abcbacb$.
对于第一个查询，$S$ 的第 $1$ 到第 $5$ 个字符组成的字符串是 $abcba$，这是回文串。因此，输出 $Yes$。
对于第二个查询，$S$ 的第 $4$ 到第 $7$ 个字符组成的字符串是 $bacb$，这不是回文串。因此，输出 $No$。
对于第三个查询，$S$ 的第 $2$ 到第 $2$ 个字符组成的字符串是 $b$，这是回文串。因此，输出 $Yes$。
对于第四个查询，将 $S$ 的第 $5$ 个字符改为 $c$。$S$ 变为 $abcbccb$.
对于第五个查询，$S$ 的第 $1$ 到第 $5$ 个字符组成的字符串是 $abcbc$，这不是回文串。因此，输出 $No$。
对于第六个查询，$S$ 的第 $4$ 到第 $7$ 个字符组成的字符串是 $bccb$，这是回文串。因此，输出 $Yes$。
对于第七个查询，将 $S$ 的第 $4$ 个字符改为 $c$。$S$ 变为 $abccccb$.
对于第八个查询，$S$ 的第 $3$ 到第 $6$ 个字符组成的字符串是 $cccc$，这是回文串。因此，输出 $Yes$。

标签: AtCoder|abc331F

来源

AtCoder|abc331F