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

上午模拟赛考了这个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)$

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×