view in my blog.

这种背包是 $\max,+$ 卷积，没法支持删除，线段树分治可以做，但是不牛。

考虑双栈模拟，左栈存队列左端，右栈存队列右端，求答案就做一个单调队列滑动窗口。为了代码方便可以把其中一个背包复制一遍，写起来比较舒服。

当一个栈弹空的时候，暴力重构两个栈，也就是把另一个栈的一半信息分过来。

这样做的复杂度如何？考虑势能分析。令势能为两栈大小之差的绝对值，每次增删会产生 $1$ 的势能，而每次重构会花费 $\mathcal O(np)$ 的代价消耗 $n$ 单位的势能。所以复杂度即为 $\mathcal O(mp)$。