Codeforces 240F: TorCoder

1.  题目大意

    给出一个长度为\(n\)的字符串,以及\(m\)个操作,每个操作给出一个区间\([l, r]\),你需要将\([l, r]\)中的字符重排使得这个子串成为一个回文串并且字典序最小。如果某个操作不可能排出回文串,则忽略这个操作。你需要输出执行完所有操作后的字符串。

 

2.  数据范围

    \(1 \le n, m \le 10^5\)

 

3.  题解

    使用线段树维护每个字符出现的次数,以及支持区间覆盖的操作。对于每个操作,查询区间内每个字符出现次数,然后按字典序重排即可。

 

4.  时空复杂度

    时间复杂度:\( O( \sigma(n +  m log n) ) \)

    空间复杂度:\( O( n \sigma ) \)

 

5.  代码

    代码在这里

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com