Bermart Ice Cream
Contest: Educational Codeforces Round 171 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, dfs and similar, divide and conquer, dp, implementation, trees

In the Bermart chain of stores, a variety of ice cream is sold. Each type of ice cream has two parameters: price and tastiness.

Initially, there is one store numbered $$$1$$$, which sells nothing. You have to process $$$q$$$ queries of the following types:

- $$$1~x$$$ — a new store opens, that sells the same types of ice cream as store $$$x$$$. It receives the minimum available positive index. The order of the types of ice cream in the new store is the same as in store $$$x$$$.
- $$$2~x~p~t$$$ — a type of ice cream with price $$$p$$$ and tastiness $$$t$$$ becomes available in store $$$x$$$.
- $$$3~x$$$ — a type of ice cream that was available the longest (appeared the earliest) in store $$$x$$$ is removed.
- $$$4~x~p$$$ — for store $$$x$$$, find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $$$p$$$ (each type can be used in the subset no more than once).

Input format:
The first line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^4$$$) — the number of queries.

Each of the following $$$q$$$ lines contains a query in the format described in the statement:

- $$$1~x$$$;
- $$$2~x~p~t$$$ ($$$1 \le p, t \le 2000$$$);
- $$$3~x$$$;
- $$$4~x~p$$$ ($$$1 \le p \le 2000$$$).

Additional constraints on the input data:

- $$$x$$$ in each query does not exceed the current number of stores (that is, $$$1$$$ plus the number of type $$$1$$$ queries);
- query type $$$3$$$ is not applied to a store that has no types of ice cream;
- there is at least one query of type $$$4$$$.

Output format:
For each query of type $$$4$$$, output a single integer — for store $$$x$$$, find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $$$p$$$ (each type can be used in the subset no more than once).

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Example input:
12
2 1 5 7
2 1 3 4
4 1 4
4 1 8
4 1 2
1 1
2 2 4 10
4 1 9
4 2 9
3 1
4 1 9
4 2 9

Example output:
4
11
0
11
17
4
17

Editorial:
Let's try to solve the problem without queries of type $$$1$$$. This leads to a data structure where elements are added to the end and removed from the beginning. In other words, a queue. The query is a dynamic programming problem of the "knapsack" type.
To implement a knapsack on a queue, we can use the technique of implementing a queue with two stacks. This is commonly referred to as a "queue with minimum", as it is usually used to maintain the minimum. You can read more about it on cp-algorithms. We replace the operation of taking the minimum with the operation of adding a new item to the knapsack in $$$O(P)$$$, where $$$P$$$ is the maximum price in the queries. This gives us a solution with a time complexity of $$$O(qP)$$$.
Now, let's return to the original problem. A type $$$1$$$ operation essentially adds the necessity to make the data structure persistent. However, this is only true if we need to respond to queries in the order they are given. In this problem, this is not the case — we can try to transition to an "offline" solution.
Let's build a version tree of our persistent structure. For each query of type $$$1$$$, $$$2$$$, or $$$3$$$, create a new version. The edge between versions will store information about the type of change: a simple copy, an addition of an element, or a deletion of an element. Queries of type $$$4$$$ will be stored in a list for each vertex to which they are addressed.
We will perform a depth-first traversal of the version tree. During the transition along an edge, we need to be able to do the following. If the transition is of the "add element" type, we need to add the element to the end, then process the subtree of the vertex, answer the queries for that vertex, and upon exiting, remove the element from the end. For a transition of the "remove element" type, we need to remove the element from the beginning and then add an element to the beginning. Thus, a structure of the "deque" type is sufficient. It turns out that a deque that maintains a minimum also exists. You can read about it in a blog by k1r1t0.
Overall complexity: $$$O(qP)$$$, where $$$P$$$ is the maximum price in the queries.