7641: [CSES Problem Set] Palindrome Queries
[Creator : ]
Description
You are given a string that consists of $n$ characters between a–z. The positions of the string are indexed $1,2,\dots,n$.
Your task is to process $m$ operations of the following types:
Your task is to process $m$ operations of the following types:
-
Change the character at position $k$ to $x$
- Check if the substring from position $a$ to position $b$ is a palindrome
Input
The first input line has two integers $n$ and $m$: the length of the string and the number of operations.
The next line has a string that consists of $n$ characters.
Finally, there are $m$ lines that describe the operations. Each line is of the form "1 k x" or "2 a b".
The next line has a string that consists of $n$ characters.
Finally, there are $m$ lines that describe the operations. Each line is of the form "1 k x" or "2 a b".
Output
For each operation 2, print YES if the substring is a palindrome and NO otherwise.
Constraints
$1≤n,m≤2⋅10^5$
$1 \le k \le n$
$1 \le a \le b \le n$
$1 \le k \le n$
$1 \le a \le b \le n$
Sample 1 Input
7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5
Sample 1 Output
YES
NO
YES