考虑离线做法,每个物品存在的时间一定是一段连续的区间。建一棵线段树按时间分治,乱搞一下。

考虑在线做法:有一个部分分是只会在一端进行插入删除操作,那么我们开个栈,插入元素就加进去,删除就弹出。复杂度 $ O ( n m ) $ ;既然我们需要在两端操作,那么我们只要维护两个这样的栈即可,查询时把两边的 dp 数组合并。暴力合并是 $ O ( m ^ 2 ) $ 的,会 TLE ,所以我们把一个数组放在线段树上,枚举另一个数组的每一个数,做一下区间查询即可。同时有个问题即有可能在前端删除从后端插入的元素,这种时候我们暴力重构两个栈,各放一半的元素,就能保证复杂度。最后总时间复杂度 $ O (n \log n \times m \log m) $ ,可以通过此题。

由于笔者在做题时把合并的 $ O (m ^ 2) $ 算成了 $ O ( m ) $ 所以去写了在线做法,还好想出了线段树才捡回一条命 233。

Your browser is out-of-date!

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

×