PROBLEM LINK:
March Lunchtime 2018
Practice
AUTHOR:
mgch
DIFFICULTY:
hard
PREREQUISITES:
Euler Tour, Segment Tree with lazy propagation, sqrt-decomposition
PROBLEM:
Please Refer links above.
Note:
My solution may have oversights or may not be optimal. Please do point them out.
SOLUTION:
First up, note that the path between two nodes a and b is the union of the path from a to p and p to b where p = \text{LCA}(a,b).
Hence the first thing we do is build the LCA structure, so that we can find p in \mathcal O(\log n) time. Also, notice that the way the question is set up suggests segment trees, yet we don’t know how to generate a segment tree on a tree. Hence we do this: arbitrarily root the tree at some vertex, and take an Euler tour of the tree. Now “flatten” out the tree by generating a sequence by this Euler tour. Note that this sequence has length exactly 2N since each node appears exactly twice in our sequence.
Now, consider a query of the second type. To find the minimum \geq X value on the path from a to b it is sufficient to query the contiguous sub-sequence \text{out}(a) \dots \text{in}(b) (or the other way round if b occurs “earlier” in our Euler tour). In this subsequence we may have stray nodes that were not on the path from a to b, but all these stray nodes occur exactly twice, hence we may detect such nodes during processing of the query.
Now, I can think of two ways to proceed from here.
In both approaches, note that the subsequence \text{out}(A) \dots \text{in} (b) does not contain exactly one node on the path from a to b : \text{LCA}(a,b). So for each query we’ll have to check one node separately, the LCA of a and b.
APPROACH 1. SQRT DECOMPOSITION
We can divide the Euler tour-array into subarrays of size \sqrt{2N}. For each subarray maintain separately a sorted version of the subarray. Whenever we have a query on an interval, do binary search on those subarrays completely covered by the interval, and on the two subintervals hanging off, perform a linear search. For updates, maintain an update box for these subarrays and just do the same as above: for subarrays completely covered by the interval, just add the value to the update box (and add this value to the results of the binary search during queries) and for the two hanging off intervals, manually update each value.
In this case,
Preprocessing takes \mathcal O(N \log N) time.
Updates take \mathcal O(\sqrt N) time.
Queries take \mathcal O(\sqrt N \log N) time. (The binary searches bring in the extra log)
Overall the time complexity is \mathcal O (N\log N + Q\sqrt N \log N). Might barely pass using fast IO.
APPROACH 2.
Build a segment tree on the Euler-path array. For every node responsible for the range (L,R), maintain a vector of sorted elements from \text{array}[L] to \text{array} [R]. To do this we build these sorted vectors bottom up, using the merge function as in mergesort to do the sorting since the two children are already sorted. Note that each cell of the array occurs in exactly 1+\log N levels, hence the cost of preprocessing the segment tree is \mathcal{O} (N \log N) amortized.
Now also store pointers from \text{in}(x) to \text{out}(x) and vice versa for every node, in this array since we want updates to \text{in}(x) to be checked when accessing \text{out}(x) and vice versa.
To handle updates, we can do standard lazy propagation. Store the update box and propagate downwards and “sideways” (i.e. from in to out and vice versa) only when accessed.
To perform queries, just perform a search in the segment tree for the interval, for the subintervals in the segtree relevant to us, perform binary search for successor of X (and add the update boxed value) to the result, and take the minimum of all these results.
Time complexity of query is \log ^2 N (since \mathcal O(\log N) intervals to binary search on, each adds \mathcal O(\log N) to the time complexity. The time complexity of update is \mathcal O (\log N).
Overall complexity is \mathcal{O}(N \log N + Q \log ^ 2 N).
I haven’t implemented this approach in code yet, so I may have made some errors above. Nevertheless, I have attempted to do it error-free.