Score : $500$ points

问题描述

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

每个查询属于以下两种类型之一：

• 1 x c：将 $S$ 中的第 $x$ 个字符替换为字符 $c$。
• 2 l r：对 $S$ 中的字符进行升序排序得到字符串 $T$。如果 $S$ 中从第 $l$ 个到第 $r$ 个字符组成的子串是 $T$ 的子串，则输出 Yes；否则输出 No。

什么是子串？子串是指通过从 $S$ 中移除 $0$ 个或多个首部字符及 $0$ 个或多个尾部字符后得到的字符串。例如，ab 是 abc 的子串，而 ac 不是 abc 的子串。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 11:56:13