Knapsack and Queries
https://jag2018summer-day2.contest.atcoder.jp/tasks/jag2018summer_day2_d
It's very interesting. The key property is a queue can be simulated by two stacks. Each push query, you can compute new values of dp in O(mod). Pop query is trivial, just ignoring the last operation. Besides, push queries is at most O(Q). So entire performance requires O(Q*mod), it is amortized. It is difficult to devise this algorithm without any suggestion.
I consider my solution is unsafe because the size of queue for sliding minimum is a little short (it must be 1000 but 500).
As I remember, a replacement a queue with two stacks are described in Introduction to Algorithms and Purely Functional Data Structures. I learned at the lecture of algorithms (Maybe it was an exercise or in a short exam).
If you have two stacks, you can simulate queue operations as described below:
enqueue 1: ([], []) -> ([1], []) enqueue 2: ([1], []) -> ([1,2], []) enqueue 3: ([1,2], []) -> ([1,2,3], []) dequeue: ([1,2,3], []) -> ([], [3,2,1]) -> ([], [3,2]) enqueue 4: ([], [3,2]) -> ([4], [3,2]) enqueue 5: ([4], [3,2]) -> ([4,5], [3,2]) dequeue: ([4,5], [3,2]) -> ([4,5],[3]) dequeue: ([4,5], [3]) -> ([4,5],[]) dequeue: ([4,5],[]) -> ([], [5,4]) -> ([], [5]) dequeue: ([], [5]) -> ([], [])
Specifically, if the second stack has at least one element, pop query returns the last element of the second stack and remove it. Otherwise, pop the first stack repeatedly until it becomes empty and each popped element is pushed to the second stack. You can realized that this operation will reverse the order of its elements. Its time complexity is O(n), n is the number of operations. This proof is easy for you.
