Back Ground

I managed to solve CF707D and at that time I didn't know this trick. After thinking for a while, I had a really good idea about solving it. After I read the tutorial I saw that this solution is mentioned in Solution No.1. But I really learned I good way of solving data structure problems including the following operations.

$$$1.$$$ Modify based on version x and the result is assigned version x

$$$2.$$$ return ... in a state they were after applying $$$k$$$-th operation.

For these questions, we could build a tree and solve the queries by DFS if off-line solutions are allowed.

Construction

The construction is quite easy. If version $$$v$$$ is modified based on version $$$x$$$, we add an edge from version $$$x$$$ to version $$$v$$$.

Because every version only has exact one father so obviously, the graph formed a tree.

Query

The answer of a query is affected by the modifications on the path from the root to this version, so what we need is to calculate it, and the way is to maintain a structure mentioned in the task without modifications based on other versions. In other words, we only need to maintain the latest version of the structure.

When we are staying at one version, we added the modifications the version contains, query for the answer and move to the children of the version.

After visiting all of its children, we should revoke the modifications if necessary.

The code goes like this:

void DFS(int u) {
  add modifications of version u
  query the ans at version u if there are queries.
  visit the children of version u
  revoke the modificationis of version u
}

Examples

No.1 707D - Persistent Bookcase

Solution: we build a tree mentioned above and use a bitset to maintain the latest version and update the answers.

No.2 GYM100431 G

Solution: build a tree mentioned above and use vector to maintain the latest version and update the answers.

There is a trick that we do not need to actually pop the first element, we only need to maintain the position of the first element and move it.

No.3 Found by sadbubbles

CSES.fi 1737

Solution: In this problem the modifications are not assigned a new version. So we try to record every history version. Use $$$lat[x]$$$ to record the index of the latest version of array $$$x$$$.

If we have queries, just add it to the latest version of array $$$x$$$ at that moment.

If we have modifications, just create a new version and add the modifications on the new version. Then update $$$lat[x]$$$.

Therefore we could solve this by DFS a tree.