比赛场次 508
比赛名称 SYOI2022 Round2
比赛状态 已结束比赛成绩
开始时间 2022-06-15 18:30:00
结束时间 2022-06-16 21:05:00
开放分组 全部用户
注释介绍
题目名称 苍空下的乐章
输入输出 Carillon.in/out
时间限制 3000 ms (3 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravataryrtiop AAAAAAAAAA 0.983 s 6.44 MiB 100
Gravatarop_组撒头屯 AATTTTTTTT 24.031 s 5.83 MiB 20
GravatarHeSn AATTTTTTTT 24.036 s 6.36 MiB 20
Gravatar该账号已注销 AATTTTTTTT 24.051 s 6.36 MiB 20

苍空下的乐章

★★   输入文件:Carillon.in   输出文件:Carillon.out   简单对比
时间限制:3 s   内存限制:256 MiB

【题目背景】

「瑟尼欧里斯」,极位古圣剑之一,相传是在古战场上奇迹般诞生的神兵利器,现存「遗迹兵器」中最强大的一把剑。

由四十一个护符组成。能将所有事物包含不死者都回归「死亡」(能对被剑伤害的人加上极为复杂的名为“死”的诅咒,连不死之躯都能“杀死”)。

而五百年后,它的能力已经无人可以动用,而剑本身也已经接近支离破碎。

只有现存的唯一一个人类,二等咒器技官「威廉·克梅修」知道它的能力和调整它的方法。

为了在接下来的战斗中让它发挥出全部的力量,威廉需要将它调整到极限状态。

夜晚,威廉带着瑟尼欧里斯,来到浮空岛的边境,在苍空的笼罩下开始了调整工作。

轻轻碰了一块于剑身中段发光的金属片。铿的轻轻一声。金属片自己从剑身卸下以后,便飘浮到半空中,停在离他大约五步远的地方。

在剑柄上注入少许魔力,向护符弹去,宛如演奏铁琴般的清脆金属声响起。光芒陆续飞舞,乐音四起。

【题目描述】

为了方便,可以将护符抽象为 $\text{a} \sim \text{z}$ 的小写字母,排开的护符则可以看做一个长度为 $n$ 的字符串 $s$。

对于调整,威廉可以进行两种操作:

$1\ l\ r\ \text{a}$,表示将 $s_l\ldots s_r$ 全部替换为 $\text{a}$。

$2\ l\ r$,表示将 $s_l\ldots s_r$ 上的字符按字典序升序排序。

(eg.字符串 $\text{dbca}$ 排序后则为 $\text{abcd}$,$\text{plcz}$ 排序后则为 $\text{clpz}$)

现在,威廉想知道,经过 $m$ 次操作后,原先的护符会变成什么样子。

【输入格式】

第一行,两个数 $n$,$m$,表示字符串的长度和操作次数。

接下来一行,一个长为 $n$ 的字符串 $s$。

后面 $m$ 行,每行一种操作,格式和含义见题目描述。

【输出格式】

一个字符串,表示 $s$ 经历 $m$ 次操作后会变为什么样。

【样例输入】

5 3
abacd
1 1 2 c
2 1 5
1 1 1 d

【样例输出】

dcccd

【样例说明】

第一次操作:$\text{ccacd}$

第二次操作:$\text{acccd}$

第三次操作:$\text{dcccd}$

【数据规模与约定】

对于 20% 的数据,$1 \le n,m \le 5\times 10^3$

对于 100% 的数据,$1 \le n,m \le 10^5$,$1 \le l \le r \le n$。

数据均为随机构造。

【来源】

sywb-lgc