102855: [AtCoder]ABC285 F - Substring of Sorted String

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.

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.

问题描述

你将得到一个长度为$N$的字符串$S$，由小写英文字母组成，以及$Q$个查询。按顺序处理这些查询。

每个查询分为以下两种类型之一：

• 1 x c：将字符串$S$中的第$x$个字符替换为字符$c$。
• 2 l r：设$T$是通过按升序排列字符串$S$中的字符得到的字符串。如果由$S$中的第$l$个到第$r$个字符组成的字符串是$T$的子串，则打印Yes；否则打印No。

约束

• $1\leq N \leq 10^5$
• $S$是一个长度为$N$的字符串，由小写英文字母组成。
• $1 \leq Q \leq 10^5$
• 对于每个第一种类型的查询，$1 \leq x \leq N$。
• 对于每个第一种类型的查询，$c$是一个小写英文字母。
• 对于每个第二种类型的查询，$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。