Knapsack and Queries

来自Petrozavodsk Winter-2018. AtCoder Contest里的D题

题意是说,有Q次操作,分为两种,一是添加一个重量为w,价值为v的物品,保证插入的w单增,二是删除当前重量最小的物品。每次操作完之后,都有一个询问,询问能否从已有物品中选出一个子集,使得重量之和在模M之后在区间[l,r]内,并且价值和最大。

数据范围,\(Q\le 100000,2\le M\le 500\)。

Q和M一开始给定,之后每次操作强制在线。

做法:首先背包比较容易看出,但是有动态的插入、删除,这里的动态实际上是队列的模型,队尾入队,队首出队。我们将所有物品分成两部分,右半部分直接组成一个背包,左半部分记录从分界线开始的所有后缀组成的背包状态。那么插入就直接背进右边,删除直接删除左边第一个物品,不影响其他后缀,当左边为空时,就将右边所有物品移到左边,即将分界线移到最右侧,然后对每个后缀求背包。查询时,只需合并一次两边的背包,可以用单调队列优化。

这样每个物品最多只会用来做两次背包,做背包和合并两个背包的时间复杂度都是\(O(M)\),所以总的时间复杂度为\(O(QM)\)。因为要记录左侧每个后缀,所以空间复杂度最多也是\(O(QM)\)。

 

代码仿照标程用了一些C++11的东西,比如template+using,swap两个vector,比较实用。