smallfang

题解 - CF558E
CF558E A Simple Task题目简述给定一个长度不超过 $10^5$ 的字符串(小写英文字母),和不超...
扫描右侧二维码阅读全文
22
2021/08

题解 - CF558E

CF558E A Simple Task

题目简述

给定一个长度不超过 $10^5$ 的字符串(小写英文字母),和不超过 $50000$ 个操作。

每个操作 L R K 表示给区间 $[L,R]$ 的字符串排序,K=1为升序,K=0为降序。

最后输出最终的字符串。

题目思路

我们考虑建26颗线段树。分别维护 $a \sim z$ 每个字符在字符串的位置。每次操作即将 $[l,r]$ 中按照升序或者降序查找$a \sim z ( or \space z \sim a) $。将他们按顺序,在按照个数(数量)依次拼接。最终按照每个字符所在位置最终输出答案即可。

Last modification:August 22nd, 2021 at 09:28 am
End.

Leave a Comment