PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This is supposed to relatively hard problem in this set. Usually the hard one in cookoffs are much harder, this time its easier than the usual hards. This problem can be solved using a standard segment tree with little tweaks.
Lets see a simpler version of this problem : Given an array A[1…n], answer a lot of queries of the form, find the top-2 maximum values in the range [i…j]. This can be solved using a standard segment tree ( actually its called a range tree ). We build a tree having O(n) nodes and each node stores the information needed, only for a certain continuous range of indices assigned to it. Given any query range, we can decompose it in to union of at most O(log n) predefined ranges and combine the results of them to obtain the answer. For this problem, we just need to maintain the top-2 maximum values in the range, at each node. This occupies O(n) space and each query can be answered in O(log n) time.
This can handle updates of the form, set A[i] = v, by updating values along the path from the leaf ( for [i…i] range ) to the root. If we know all the queries before hand, we can sort them and process in that order, using the standard segment tree. Here, a query also depends on the result of the previous query and so we need online processing of the queries. A query can also be made on a previous version of the array, so we can not overwrite the old values along the path. But, we create a new duplicate path corresponding to this and update this new path. Note that a path has only O(log n) nodes and processing Q queries will require additional O(Q logn) space. Each query is just the standard O(log n) time segment tree query, except that we need to start at the root corresponding to the queried version. This is a very basic problem in the category of data structures called Persistent data structures, where information about the past is also stored. Better solutions for this are available, but the simple method explained above works for this problem. Hope to see such problems in various contests.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.