F - Palindrome Query Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。
以下で説明されるクエリを与えられる順に Q 個処理してください。
クエリは次の 2 種類のいずれかです。

  • 1 x c : S の x 文字目を英小文字 c に変更する。
  • 2 L R : S の L 文字目から R 文字目までからなる部分文字列が回文であるならば 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 番目のクエリについて、S の 1 文字目から 5 文字目までからなる文字列は abcba で、これは回文です。よって Yes を出力します。
2 番目のクエリについて、S の 4 文字目から 7 文字目までからなる文字列は bacb で、これは回文ではありません。よって No を出力します。
3 番目のクエリについて、S の 2 文字目から 2 文字目までからなる文字列は b で、これは回文です。よって Yes を出力します。
4 番目のクエリについて、S の 5 文字目を c に変更します。S は abcbccb になります。
5 番目のクエリについて、S の 1 文字目から 5 文字目までからなる文字列は abcbc で、これは回文ではありません。よって No を出力します。
6 番目のクエリについて、S の 4 文字目から 7 文字目までからなる文字列は bccb で、これは回文です。よって Yes を出力します。
7 番目のクエリについて、S の 4 文字目を c に変更します。S は abccccb になります。
8 番目のクエリについて、S の 3 文字目から 6 文字目までからなる文字列は cccc で、これは回文です。よって Yes を出力します。

Score : 525 points

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.