排序后字符串的子串

题目描述

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

每个查询是以下两种类型之一:

• 1 x c:将 $S$ 的第 $x$ 个字符替换为字符 $c$。
• 2 l r:设 $T$ 为将 $S$ 的字符按升序排序后得到的字符串。如果由 $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$

输出格式

按照题目描述处理查询。

样例

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

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。

数据范围

• $1 \le N \le 10^5$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。
• $1 \le Q \le 10^5$
• 对于第一种查询,$1 \le x \le N$。
• 对于第一种查询,$c$ 是小写英文字母。
• 对于第二种查询,$1 \le l \le r \le N$。