[学习笔记]尺取法维护不支持删除的信息

上午模拟赛考了这个trick，然后我不会，学会了来写一波博客。

考虑一类求最短区间的问题，满足单调性（可以two-pointers），插入很快，但是删除很慢，不过可以快速的判断两段的信息合并能否满足条件。

这时普通的尺取法就没法用了。

怎么解决呢？

（假设插入和合并是$O(1)$）

算法1

考虑计算通过中心的答案，然后分治。

具体的，计算[i,mid]和[mid+1,r]的区间信息，由于满足单调性，所以可以two-pointers计算答案。

时间复杂度$O(n\log n)$

然而有的题过不了

算法2

考虑用两个栈来维护信息，第一个栈维护当前[l,mid]区间中每一个后缀的信息（左端点从顶到底分别是l,l+1,$\dots$,mid)，第二个栈维护[mid+1,r]的信息（实际上并不需要栈？）。

那么每次++r就是压一个新元素进第二个栈，++l就是第一个栈弹出一个。如果第一个栈空了，就把第二个栈整个放进第一个栈里面。

然后做完了。

时间复杂度$O(n)$。

例题 小$\omega$的仙人掌

题面

小$\omega$有s个物品，每个物品有一定的大小与权值。

她可以从任意第L个物品走到第R个物品，这个区间内的物品可以选或者不选。

她取出的物品大小和必须为w,权值和必须<= k。

她想知道这个区间最短是多少。

你能告诉她吗？

$s\le 10000,w\le 5000$。

做法

维护背包。合并判断就是枚举左边大小为x右边为w-x。

时间复杂度$O(sw)$