← 返回题目列表

AtCoder · KeioPC2025_r

R. 许多字符串

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

配点 : 100 点

問題文

长度 小于或等于 N 的字符串 S 。另外,用空字符串初始化 2\times10^5 字符串 T_1, T_2, \ldots , T_{200000} 。
按以下格式给出 按给定顺序处理 Q 查询。
查询是: 2 其中一种。

  • 类型 1: 它以 1 k l r 格式给出。T_k 该值应乘以 T_k 和 按字典顺序比较 S 可以得到第 l 从第一个字符开始 r 将最多包含字符数的子字符串替换为按该顺序的连接。

  • 类型 2: 2 x y 格式给出。 T_x 更好 如果按字典顺序大于 T_y 如果按字典顺序大于 > 如果更小 < ,如果相等 = 。 我锻炼

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • S 是小写字母的长度 N 的字符串
  • 1 \leq k \leq 2 \times 10^5
  • 1 \leq l \leq r \leq N
  • 1 \leq x,y \leq 2 \times 10^5
  • x \neq y
  • N,Q,k,l,r,x,y 是一个整数

入力

输入是按以下格式从标准输入给出的。

N\ Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均以以下格式之一给出:

1\ k\ l\ r
2\ x\ y

出力

类型 2 的查询数量 q 次 q 行。
j 类型 2 的查询 j 打印该项目的答案。


入力例 1

10 7
keioprocon
1 1 1 4
1 2 5 10
2 1 2
1 3 1 10
1 1 5 10
2 1 3
2 1 4

出力例 1

<
=
>
  • 1 第查询: 将 T_1 该值应乘以 T_1 和 按字典顺序比较 keio 替换为串联。更换后 将 T_1 是 您也可以写 keio 。
  • 2 第查询: 将 T_2 该值应乘以 T_2 和 按字典顺序比较 procon 替换为串联。 ,替换后 比较 T_2 是 您也可以写 procon 。
  • 3 第查询: 将 T_1 和 按字典顺序比较 T_2 。T_1 = keio , T_2 = procon ,按字典顺序比较时, T_1 较小,因此 输出 < 。
  • 4 第查询: 将 T_3 该值应乘以 T_3 和 按字典顺序比较 keioprocon 替换为串联。更换后 将 T_3 是 您也可以写 keioprocon 。
  • 5 第查询: 将 T_1 该值应乘以 T_1 和 按字典顺序比较 procon 替换为串联。更换后 将 T_1 是 您也可以写 keioprocon 。
  • 6 第查询: 将 T_1 和 按字典顺序比较 T_3 。T_1 = keioprocon , T_3 = keioprocon 和 按字典顺序相等。 = 。
  • 7 第查询: 将 T_1 和 按字典顺序比较 T_4 。T_1 = keioprocon , T_4 是一个空字符串,按字典顺序比较时, T_4 较小,因此 输出 > 。