Subtask 1

For the first subtask, we can create a copy of the graph and the value of each of the nodes for each query. We can perform the second and third actions by performing a breadth first search or depth first search from city ~a_i~.

Time Complexity: ~\mathcal O(QN)~
Memory Complexity: ~\mathcal O(QN)~

Subtask 2

For the second subtask, we only need to keep track of one version of the graph at a time, and do not have to worry about type ~3~ actions. We can think of the first action as merging two sets together. If we use a data structure such as a priority queue, we can then query for the maximum value in each set in ~\mathcal O(\log N)~ time. To merge sets together efficiently, we can use small to large merging where all elements in the smaller set are merged into the larger set for an amortized time complexity ~\mathcal O(\log^2 N)~ for each merge. Alternatively, one can use pairing heaps or leftist heaps for a worst case time complexity of ~\mathcal O(\log N)~, randomized heaps for an expected time complexity of ~\mathcal O(\log N)~, or skew heaps for an amortized time complexity of ~\mathcal O(\log N)~. Finally, to determine which set a node is currently in, we can use the Union-Find data structure to find the root of each set in amortized ~\mathcal O(\alpha(N))~ time if both union find by size (or rank) and path compression is used.

Time Complexity: ~\mathcal O(N + Q \log^2 N)~ if small to large merging is used, ~\mathcal O(N + Q \log N)~ if mergeable heaps are used
Memory Complexity: ~\mathcal O(N)~

Subtask 3

For the third subtask, we can handle type ~3~ actions by maintaining an offset for each heap, representing the amount every element in that heap has been incremented. We will have to add this offset when accessing or removing a value inside the heap, and subtract the offset when inserting a value into the heap. Alternatively, if mergeable heaps are used, we can store a lazy value in each node, and lazily propagate that value down as we access the nodes.

Time Complexity: ~\mathcal O(N + Q \log^2 N)~ if small to large merging is used, ~\mathcal O(N + Q \log N)~ if mergeable heaps are used
Memory Complexity: ~\mathcal O(N)~

Subtask 4

For the fourth subtask, we will need to quickly store and retrieve previous versions of the heaps and Union-Find data structures. For the array representing the Union-Find data structure, we can use a persistent array. The persistent array can be represented with a balanced binary search tree with ~N~ nodes. Every time a node is accessed, a new node is created and returned to its parent. We can store the root node of this tree for each version of the data structure. Note that the amortized time complexity of path compression does not apply as there are cases where the same long path is compressed over multiple versions of the data structure and can increase the memory required (thank you bqi343 for pointing this out). Each find operation takes ~\mathcal O(\log^2 N)~ time.

We can also make the heap persistent by creating and returning new nodes to its parent every time a node is accessed. Note that skew heaps cannot be used as amortization does not apply, and the worst case time complexity is ~\mathcal O(N)~ per operation (though data may not have been strong enough to stop all variants of skew heaps). We can then use a persistent array to keep track of the root nodes of each set. Note that ~\mathcal O(\log N)~ nodes could be created in each operation of the persistent heap.

Time Complexity: ~\mathcal O(N + Q \log^2 N)~
Memory Complexity: ~\mathcal O(N + Q \log N)~

Subtask 5

For the full solution, we can combine both the persistent data structures in subtask ~4~ and the lazy propagation in subtask ~3~.

Time Complexity: ~\mathcal O(N + Q \log^2 N)~
Memory Complexity: ~\mathcal O(N + Q \log N)~