(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
HARD
PREREQUISITES:
heavy-light decomposition, hashing, segment trees
PROBLEM:
Just another problem with queries on a tree. The queries are: reverse values on a path, copy values from a path, check if two paths contain the same sequence of values.
QUICK EXPLANATION:
Comparing paths = comparing hashes. Reversal queries are irrelevant. Use HLD to reduce the problem to subarray copy / compute hash queries, which can be solved using persistent DS, e.g. persistent segment trees.
EXPLANATION:
Queries of type 1 are just copying a path u\rightarrow v to the path v\rightarrow u, so we can just deal with them the same way as with type 2 queries.
This problem combines many advanced concepts. The first and probably most basic one is using heavy-light decomposition of the tree (rooted at e.g. 0) to split any path to O(\log{N}) paths, where each path goes towards or away from the root. When we have two paths of equal lengths, we can put them side by side and split each of them also at the same positions where the other is split; that gives still O(\log{N}) pairs of paths p_{1i},p_{2i} of equal lengths such that we need to copy the values in p_{1i} to p_{2i} for each i or check if they’re equal for each i.
The benefit of this splitting is that each path in the HLD is a linear structure - the copy/check operations are now on subarrays/segments (of possibly different arrays or the same array) instead of arbitrary paths in a tree.
SEGMENT OPERATIONS
First of all, checking subarrays/segments for equality directly is slow. We need some way to compare two segments in constant time, and the common choice for this is hashing. Let’s use a polynomial hash H(s)=\sum s_i q^i \% p for p=10^9+7 and some number q. If two segments have equal hashes, then they’re equal and if we know the lengths and hashes of two segments, we can compute their hash in constant time using precomputed powers of q. Let’s also not forget that the paths in the tree and therefore also segments here can be directed, so we need to store both forward and reverse hashes.
Let’s now build the typical data structure for segment operations: a segment tree which supports copying a segment (possibly from a different segment tree) and computing a segment’s hash. Most of the implementation is the same as for any other segment tree: if the current vertex doesn’t correspond to the current segment, split into sons and merge their hashes into the current vertex’s hash, return the hash of the current vertex when asked for it. The problem is the copy operation: what to do when a segment corresponding to some vertex v_1 has to be copied to another segment corresponding to some vertex v_2?
This trick is what persistent structures are based on: we simply replace the edge to v_1 from its parent (the vertex we got into it from) by an edge from that parent to v_2. Of course, when copying something into the subtree of such a vertex, we have to be careful: that vertex is shared by multiple segment trees, but we’re only modifying it in one of them. The solution is to create a copy of it with the same sons and only one parent - the one from the currently modified subtree. (Note that a vertex can technically have multiple parents, but they belong to different trees; this procedure also ensures that only the currently processed vertex can have multiple parents and not any vertices above it, since they’re the copies created here. We don’t have to remember the parents; they’re given implicitly when we go down a tree.)
In order to avoid having to reverse whole subtrees, we can mark vertices as “reverse this when necessary”; when processing such a vertex (after the above mentioned copying), we just swap its sons, mark them the same way and swap the forward/reverse hash. Also, two reversals cancel out.
We have everything necessary now. The total time complexity of any operation on such a segment tree is still O(\log{N}), since we’re only doing O(1) operations per vertex; with O(\log{N}) operations per query, the total time complexity is O(N+Q\log^2{N}). However, we’re adding O(\log{N}) vertices in each operation, so the memory complexity is also O(N+Q\log^2{N}).
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.