4199: [Noi2015]品酒大会

竟然一遍ac了...万万没想到...

容易想到先求出SA,在hight数组上乱搞即可。。。

那么算某一个r就是区间min>=r的连续一段的组合之和。

考虑算多个r,因为大r肯定包含小r,那么算出了大r最后加到小r即可。

考虑这样怎么算,用单调栈维护一下即可,但是要注意在维护单调时弹出点对于他前一个一定多加了,要减回去,

以及如果前一个点值小于当前hi,就会少算,实际就可以把此时的htop当成hi即可。

那么对于所有r就可以求出了。

考虑求出所有r其中能组成的最大值,记录下最大最小值,弹出的时候合并即可,细节具体见代码...

c++代码如下:

 

2 + 7 =