LG2827 [NOIP2016 提高组] 蚯蚓
用单调队列简单维护就可以做到 $O(m\log m) $，但 \(m\) 有点大，我们就需要考虑特殊性质。
注意到每次切割的蚯蚓长度一定小于前几次切割的长度（指的是没有每天增加 \(q\) 的情况下）。
这样考虑使用队列 \(q[3]\) 分别维护还没有切割的，切割后左边的，切割后右边的即可。
时间复杂度 \(O(m)\)。
另外读入的数组并不是单调的，但是给出的样例却都是单调的。
数据结构做题笔记
发布时间 2023-03-27 14:44:21作者: JackieXu