Skip to content

11636: 【原1636】冬季恋歌

题目

题目描述

author: aki 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1636 ## Description

传达不到的爱恋 第二幕 第三场(废)

冬木榛名,喜欢着钢琴。

一心希望谱出不被认为外行的曲谱的她,却感到了一些困扰。

冬木榛名,喜欢着雪音。

一定要来得及让雪音将这首属于三人的曲子唱出来。

冬木榛名,喜欢着和希。

可她现在眼前只有一串杂乱的音符。于是她开始尝试一些充满幻想的编曲方法。

她每次能做的,是将一段连续的音符取出来,重新组合变成对称的样子,再放回去。

如果怎么样都无法让其变得对称起来,便只能放弃这一次尝试。

如果变成对称的方法有很多种,她会选择字典序最小的那一种。

一次一次的操作实在是太慢了,请你提供一种方法,能够让她直接得到最后的曲谱吧。

快点,再快一点,时间已经不太够了。

Input Format

第一行是一个字符串,描述初始的音符序列。每一个音都是全音,即只会有C,D,E,F,G,A,B这几种。

接下来是一个数\(q\),描述操作个数。

对于之后的\(q\)行,每行描述一个事件。

  • l r,将\([l, r]\)里面的音符取出变成对称的样子放回。如果有多种方法,选择字典序最小的那一种。如果无法做到,则忽略这一次操作。

Output Format

一行,输出操作完成后的音符序列。

Sample Input

GGGDGABAGA
1
5 9

Sample Output

GGGDAGBGAA

Limits

  • 对于60%的数据,序列长度\(L \leq 500\),\(q \leq 500\)
  • 对于100%的数据,序列长度\(L \leq 100000\),\(q \leq 50000\)

Closing

舍弃了钢琴的榛名,留在了和希的身边。

而无法做出割舍的雪音,只留下了唱歌一条路。

所以雪音歌唱着。

那首将他们三人融为一体的歌。

那首让他们不再是三个毫不相干的陌生人的充满回忆的歌。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!