F - Substring of Sorted String

Contest Duration: 2023-01-15(Sun) 12:00 - 2023-01-15(Sun) 13:40 (local time) (100 minutes) Back to Home

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$

出力

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

入力例 1Copy

Copy

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

出力例 1Copy

Copy

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 1Copy

Copy

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

Sample Output 1Copy

Copy

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.