← 返回题目列表

AtCoder · abc331_f

I. 回文查询

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成。
流程 Q 下面按给出的顺序描述查询。
有两种类型的查询:

  • 1 x c :更改 x- 第一个字符 S 改为小写英文字母 c.
  • 2 L R :如果由 L-th 通过 R第一个字符 S 是一个回文,打印 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.
对于第一个查询,由 1-st 通过 5第一个字符 S is abcba,这是一个回文。因此,打印 Yes.
对于第二个查询,由 4-th 通过 7- 第一个字符 S is bacb,这不是回文。因此,打印 No.
对于第三个查询,由 2-nd 通过 2-nd 字符 S is b,这是一个回文。因此,输出 Yes.
对于第四个查询,更改 5- 第一个字符 S to c. S 变为 abcbccb.
对于第五个查询,由 1-st 通过 5- 第一个字符 S is abcbc,这不是回文。因此,输出 No.
对于第六个查询,由 4-th 通过 7- 第一个字符 S is bccb,这是一个回文。因此,输出 Yes.
对于第七个查询,更改 4- 第一个字符 S to c. S 变为 abccccb.
对于第八个查询,由 3-rd 通过 6- 第一个字符 cccc,这是一个回文。因此,输出 Yes.