不难发现每个物品的存在时间是一个区间,于是离线可以考虑线段树分治直接解决。
在线做法比较新奇,用两个栈模拟双端队列。
具体的,维护两个栈 (stkl) 和 (stkr),在开头和结尾插入删除就直接在这两个栈中分别 push 和 pop。
如果出现删除时某个栈空了,那么直接暴力重构这两个栈使得这两个栈大小之差最小。
这样做为什么是对的呢?
设 (w) 为两栈的大小之差,那么一次正常的插入删除只会让 (w) 变化 (1),而重构平均分配的操作会用 (cal{O}(w)) 的复杂度使 (w) 变成 (0) 或 (1)。均摊下来复杂度是 (cal{O}(m)) 的。
在操作过程中顺便维护一下背包数组 (dpl) 和 (dpr)。
求答案时维护一个数组 (mxr_{i,j}) 表示 ([i,i+2^j]) 的范围中 (dpr) 的最大值,枚举 (stkl) 中选多少个然后分类讨论求一下 max 即可。
具体实现细节参考 代码。