链接: https://cses.fi/problemset/task/2420

板块: String Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个由 $n$ 个 a–z 之间字符组成的字符串。字符串的位置下标为 $1,2,\dots,n$。你的任务是处理 $m$ 个如下类型的操作：

1. 将位置 $k$ 处的字符修改为 $x$
2. 判断从位置 $a$ 到位置 $b$ 的子串是否为回文

输入

第一行输入包含两个整数 $n$ 和 $m$：字符串的长度和操作个数。

下一行包含一个由 $n$ 个字符组成的字符串。

最后有 $m$ 行描述这些操作。每行格式为 "$1$ $k$ $x$" 或 "$2$ $a$ $b$"。

输出

对于每个第 2 类操作，如果子串是回文则输出 YES，否则输出 NO。

数据范围

$1 \le n, m \le 2 \cdot 10^5$ $1 \le k \le n$ $1 \le a \le b \le n$

样例输入

7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5

样例输出

YES
NO
YES