似乎是去年省选集训的时候见过啊ovo还记得当年因为把背包写错了所以被唱歌了ovo
比较有意思的题.这个题询问数是骗人的ovo其实是预处理然后O(1)询问.
把如果强行预处理的话时间是O(n3)的.于是考虑一些奇怪的黑暗.把物品强行分块.对于每一个块,可以知道它左边的总答案,右边的总答案.这个是可以O(n2)的.(二进制背包的log就忽略了)然后把左边和右边合并一下,这个是平方的.然后对于块内的每个物品,把其它的物品拿来强行跑一遍背包,这个对于一个物品的复杂度是O(n1.5)的.于是就奇妙地少了O(n0.5)的复杂度.然后就可过了ovo
我当年是怎么想到的ovo还是我当年黑暗过去了ovo