codeforces 558 E. A Simple Task (线段树优化计数排序)

题目链接

题意:给出一个字符串,仅由小写字母组成。现在给出q个操作,每个操作l,r,k三个参数,k=1表示把区间[l,r]变为升序排列,k=0表示把区间[l,r]变为降序排列。

思路:首先,最重要的一点是,由于只有26个字母,联想到计数排序。

对于字符集数目比较小情况,一定要想到计数排序。

对于字符集数目比较小情况,一定要想到计数排序。

对于字符集数目比较小情况,一定要想到计数排序。

那么我们回顾计数排序,不妨考虑升序排列的情况,是怎么做的呢?

做法是统计该区间中每种字符的个数,然后按照字符的大小,从小到大在区间上从左到右得放置每种字符。

大概是这样子:

然而这个复杂度每次是o(n)的。。。

我们需要用线段树来优化计数排序的过程。。。

思考计数排序其实分为两个过程:

一是统计某区间中每个字符的个数。

二是将字符按照字符的大小顺序重新放回区间。

 

我们可以建26棵线段树,一种字母对应一棵。

对于过程一,我们可以直接query.

对于过程2,由于相同的字母总是相邻在一起的,因此可以用线段树成段更新来优化,也就是lazy标记。

tree[id][rt]表示第id棵线段树对应的区间中字母id+’a’-1的个数。

lazy[id][rt]三种值,-1表示没有标记,0表示重置标记,1表示被某种字母覆盖的标记。(重置的意思是,该区间被排序了,但是还不确定该区间上字母是哪些)

输出的时候,对于某个位置,只要query到26个字母中值不为0的那个输出就好了。

总的复杂度:O(26*q*lgn)

代码注释中还有部分细节和理解

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz