Score : $525$ points

问题描述

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

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

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 01:16:08