103315: [Atcoder]ABC331 F - Palindrome Query

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.
Process $Q$ queries described below in the order they are given.
There are two types of queries:

• 1 x c : Change the $x$-th character of $S$ to the lowercase English letter $c$.
• 2 L R : If the substring formed by the $L$-th through $R$-th characters of $S$ is a palindrome, print Yes; otherwise, print No.

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 10^5$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• $1 \leq x \leq N$
• $c$ is a lowercase English letter.
• $1 \leq L \leq R \leq N$
• $N, Q, x, L, R$ are integers.

Input

The input is given from Standard Input in the following format. Here, $\text{query}_i$ is the $i$-th query to be processed.

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

Each query is given in one of the following formats:

$1$ $x$ $c$

$2$ $L$ $R$

Output

Follow the instructions in the problem statement and print the answers to the queries, separated by newlines.

Sample Input 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

Sample Output 1

Yes
No
Yes
No
Yes
Yes

Initially, $S =$ abcbacb.
For the first query, the string formed by the $1$-st through $5$-th characters of $S$ is abcba, which is a palindrome. Thus, print Yes.
For the second query, the string formed by the $4$-th through $7$-th character of $S$ is bacb, which is not a palindrome. Thus, print No.
For the third query, the string formed by the $2$-nd through $2$-nd character of $S$ is b, which is a palindrome. Thus, output Yes.
For the fourth query, change the $5$-th character of $S$ to c. $S$ becomes abcbccb.
For the fifth query, the string formed by the $1$-st through $5$-th character of $S$ is abcbc, which is not a palindrome. Thus, output No.
For the sixth query, the string formed by the $4$-th through $7$-th character of $S$ is bccb, which is a palindrome. Thus, output Yes.
For the seventh query, change the $4$-th character of $S$ to c. $S$ becomes abccccb.
For the eighth query, the string formed by the $3$-rd through $6$-th character of cccc, which is a palindrome. Thus, output Yes.

问题描述

你将得到一个长度为$N$的字符串$S$，由小写英文字母组成。
按照给出的顺序处理$Q$个查询。
查询有两种类型：

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

约束条件

• $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$都是整数。

输入

输入从标准输入按以下格式给出。其中，$\text{query}_i$是要处理的第$i$个查询。

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

每个查询按以下之一给出格式：

$1$ $x$ $c$

$2$ $L$ $R$

输出

按照问题描述中的说明进行操作，并在新行之间用换行符分隔打印查询答案。

样例输入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

最初，$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。
对于第八个查询，由字符串cccc的第$3$个到第$6$个字符组成的子串是回文串。因此输出Yes。