F - Substring of Sorted String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

英小文字からなる長さ N の文字列 S と Q 個のクエリが与えられます。クエリを順に処理してください。

クエリは以下の 2 種類です。

  • 1 x c ： S の x 文字目を文字 c に置き換える
  • 2 l r ： S を文字の昇順に並び替えて得られる文字列を T とする。S の l 文字目から r 文字目までからなる文字列が T の部分文字列であるとき Yes、部分文字列でないとき No を出力する
部分文字列とは？ S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

  • 1\leq N \leq 10^5
  • S は英小文字からなる長さ N の文字列
  • 1 \leq Q \leq 10^5
  • 1 種類目のクエリにおいて、1 \leq x \leq N
  • 1 種類目のクエリにおいて、c は英小文字
  • 2 種類目のクエリにおいて、1 \leq l \leq r \leq N

入力

入力は以下の形式で標準入力から与えられる。ただし、\text{query}_i で i 番目のクエリを表す。

N
S
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

出力

問題文中の指示に従ってクエリを処理せよ。

入力例 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

出力例 1

Yes
No
Yes
  • 1 番目のクエリにおいて、S を文字の昇順に並び替えて得られる文字列 T は abccdf です。 S の 1 文字目から 3 文字目までからなる文字列は abc であり T の部分文字列です。よって Yes を出力します。
  • 2 番目のクエリにおいて、S を文字の昇順に並び替えて得られる文字列 T は abccdf です。 S の 2 文字目から 6 文字目までからなる文字列は bcdcf であり T の部分文字列ではありません。よって No を出力します。
  • 3 番目のクエリにより、S の 5 文字目が e に置き換えられ、S は abcdef となります。
  • 4 番目のクエリにおいて、S を文字の昇順に並び替えて得られる文字列 T は abcdef です。 S の 2 文字目から 6 文字目までからなる文字列は bcdef であり T の部分文字列です。よって Yes を出力します。

Score : 500 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and Q queries. Process the queries in order.

Each query is of one of the following two kinds:

  • 1 x c : replace the x-th character of S by the character c.
  • 2 l r : let T be the string obtained by sorting the characters of S in ascending order. Print Yes if the string consisting of the l-th through r-th characters of S is a substring of T; print No otherwise.
What is a substring? A substring of S is a string obtained by removing 0 or more initial characters and 0 or more final characters of S. For example, ab is a substring of abc, while ac is not a substring of abc.

Constraints

  • 1\leq N \leq 10^5
  • S is a string of length N consisting of lowercase English letters.
  • 1 \leq Q \leq 10^5
  • For each query of the first kind, 1 \leq x \leq N.
  • For each query of the first kind, c is a lowercase English letter.
  • For each query of the second kind, 1 \leq l \leq r \leq N.

Input

The input is given from Standard Input in the following format, where \text{query}_i denotes the i-th query:

N
S
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Output

Process the queries as instructed in the Problem Statement.

Sample Input 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

Sample Output 1

Yes
No
Yes
  • In the 1-st query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string abc, consisting of the 1-st through 3-rd characters of S, is a substring of T, so Yes should be printed.
  • In the 2-nd query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string bcdcf, consisting of the 2-nd through 6-th characters of S, is not a substring of T, so No should be printed.
  • The 3-rd query sets the 5-th character of S to e, making S abcdef.
  • In the 4-th query, abcdef is the string T obtained by sorting the characters of S in ascending order. The string bcdef, consisting of the 2-nd through 6-th characters of S, is a substring of T, so Yes should be printed.