数据结构做题笔记

LG2827 [NOIP2016 提高组] 蚯蚓

用单调队列简单维护就可以做到 $O(m\log m) $，但 \(m\) 有点大，我们就需要考虑特殊性质。

注意到每次切割的蚯蚓长度一定小于前几次切割的长度（指的是没有每天增加 \(q\) 的情况下）。

这样考虑使用队列 \(q[3]\) 分别维护还没有切割的，切割后左边的，切割后右边的即可。

时间复杂度 \(O(m)\)。

另外读入的数组并不是单调的，但是给出的样例却都是单调的。