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)

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

 

 

 

 

hdu 1280 前m大的数 (计数排序)

hdu1280

题意:给出n(3000)个数,两两求和,输出最大的m(5000)个和。

思路:由于数据有限,想到计数排序。。。以及,m个可能刚好某个数据没有全部输出,要在while里判断一下。。

。。。好好的人。。怎么开始刷水了。。。。。

其实是因为最近在看.suffix array…然后里面涉及到了radix sort..算法课的时候到是写过。。。不过快忘了orz。。所以打算找几道题目。。。? 然而这是计数排序不是基数排序啊摔/!