AT_abc285_f [ABC285F] Substring of Sorted String

题目描述

给定一个由小写英文字母组成、长度为 $N$ 的字符串 $S$，以及 $Q$ 个查询。请依次处理这些查询。

查询有以下两种类型：

• 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 的子串。

输入格式

输入按以下格式从标准输入给出。其中，$\text{query}_i$ 表示第 $i$ 个查询。

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

输出格式

请按照题目要求依次处理每个查询。

输入输出样例 #1

输入 #1

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

输出 #1

Yes
No
Yes

说明/提示

限制条件

• $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$

样例解释 1

• 对于第 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。

由 ChatGPT 4.1 翻译