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

大爷的字符串题： 大爷们太厉害了，甘拜下风 这个题充分考察了大家的语文水平 可以发现这个乱七八糟的题面，本质是每次从区间中取出一个严格上升的序列，然后问最少取几次 由于是严格上升，所以只和相同的数个数有关，即要用区间出现次数最大的那个数出现次数那么多次 从上句话可以看出这出题人语文没救 即要求区间众数 用膜队+值域分块的方法可以O( msqrt( n ) )解决这个问题 什么？你不会值域分块？ 没事，你可以用个堆，O( msqrt( n )logn )，因为有人这样写过掉了。。。具体怎么回事我也不知道 可以参考某省省选有道数据结构题也出了同样的事情 ----------------------------- UPDATE:似乎不用值域分块。。。 我可能白学了数据结构