← 返回题目列表

AtCoder · abc285_f

I. 已排序字符串的子字符串

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成,以及 Q 查询。 按顺序处理查询。

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

  • 1 x c :替换 x- 第一个字符 S 按字符 c.
  • 2 l r :让 T 是对字符进行排序得到的字符串 S 按升序排列。 打印 Yes 如果字符串包含 l-th 通过 r- 第一个字符 S 是以下子串 T;打印 No 否则。
什么是子串? A 子字符串 长度为 $$$l$$$ 的字符串 $$$s_1s_2 \ldots s_l$$$ 的 of S 是删除后得到的字符串 0 或更多初始字符并且 0 或更多结尾字符 S。 例如, ab 是以下子串 abc,同时 ac 不是以下的子串 abc.

约束

  • 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-st 查询, abccdf 是字符串 T 通过对字符进行排序得到 S 按升序排列。 字符串 abc,包括 1-st 通过 3-rd 字符 S是以下子串 T,所以 Yes 。
  • 在 2-nd 查询, abccdf 是字符串 T 通过对字符进行排序得到 S 按升序排列。 字符串 bcdcf,包括 2-nd 通过 6- 第一个字符 S,不是以下的子串 T,所以 No 。
  • 的 3-rd 查询设置 5- 第一个字符 S to e, 制作 S abcdef.
  • 在 4第一个查询, abcdef 是字符串 T 通过对字符进行排序得到 S 按升序排列。 字符串 bcdef,包括 2-nd 通过 6- 第一个字符 S是以下子串 T,所以 Yes 。