比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
yrtiop | AAAAAAAAAA | 0.983 s | 6.44 MiB | 100 |
op_组撒头屯 | AATTTTTTTT | 24.031 s | 5.83 MiB | 20 |
HeSn | AATTTTTTTT | 24.036 s | 6.36 MiB | 20 |
该账号已注销 | AATTTTTTTT | 24.051 s | 6.36 MiB | 20 |
「瑟尼欧里斯」,极位古圣剑之一,相传是在古战场上奇迹般诞生的神兵利器,现存「遗迹兵器」中最强大的一把剑。
由四十一个护符组成。能将所有事物包含不死者都回归「死亡」(能对被剑伤害的人加上极为复杂的名为“死”的诅咒,连不死之躯都能“杀死”)。
而五百年后,它的能力已经无人可以动用,而剑本身也已经接近支离破碎。
只有现存的唯一一个人类,二等咒器技官「威廉·克梅修」知道它的能力和调整它的方法。
为了在接下来的战斗中让它发挥出全部的力量,威廉需要将它调整到极限状态。
夜晚,威廉带着瑟尼欧里斯,来到浮空岛的边境,在苍空的笼罩下开始了调整工作。
轻轻碰了一块于剑身中段发光的金属片。铿的轻轻一声。金属片自己从剑身卸下以后,便飘浮到半空中,停在离他大约五步远的地方。
在剑柄上注入少许魔力,向护符弹去,宛如演奏铁琴般的清脆金属声响起。光芒陆续飞舞,乐音四起。
为了方便,可以将护符抽象为 $\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