#T2205. 回文查询(Palindrome Queries)

回文查询(Palindrome Queries)

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

板块: String Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

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

  1. 将位置 kk 处的字符修改为 xx
  2. 判断从位置 aa 到位置 bb 的子串是否为回文

输入

第一行输入包含两个整数 nn 和 mm:字符串的长度和操作个数。

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

最后有 mm 行描述这些操作。每行格式为 "11 kk xx" 或 "22 aa bb"。

输出

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

数据范围

1≤n,m≤2⋅1051 \le n, m \le 2 \cdot 10^5 1≤k≤n1 \le k \le n 1≤a≤b≤n1 \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