题解 P3709 【大爷的字符串题】

2017-04-16 23:37:41


大爷的字符串题:

大爷们太厉害了,甘拜下风

这个题充分考察了大家的语文水平

可以发现这个乱七八糟的题面,本质是每次从区间中取出一个严格上升的序列,然后问最少取几次

由于是严格上升,所以只和相同的数个数有关,即要用区间出现次数最大的那个数出现次数那么多次

从上句话可以看出这出题人语文没救

即要求区间众数

用膜队+值域分块的方法可以O( msqrt( n ) )解决这个问题

什么?你不会值域分块?

没事,你可以用个堆,O( msqrt( n )logn ),因为有人这样写过掉了。。。具体怎么回事我也不知道

可以参考某省省选有道数据结构题也出了同样的事情


UPDATE:似乎不用值域分块。。。

我可能白学了数据结构