配点 : 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 较小,因此 输出>。