Solution for problem Verkhoyansk
O(N * Q)
Brute-Force. Process queries online, as you read then from input. Use a bool array visited and go from the left end to the right end of the query interval and mark the heights seen as visited. Then go with the supposed ans from 1 and increase it while visited[and] is true. Don't forget to reset to 0 the values in visited in order to be used correctly for the next queries.
O(N * sqrt(Q) + Q * logQ)
Divide the array of heights into contiguous buckets of size K. There will be N / K such buckets. K must not necessarily divide N. The last bucket can have a smaller size.
We will answer offline to the given mex range queries. For each bucket, we will consider all queries having the left end in the selected bucket and answer all of them. After we have taken into consideration all buckets, all queries will have found their answer and we can print them in order.
Suppose we want to compute the answers for all queries having the left end in some bucket B. Their right ends can be arbitrarily high, but their left ends are all in some interval from B * K to (B + 1) * K - 1. We will call the heights found in this interval special. All other heights are not special.
There are at most K special heights and at most K + 1 contiguous intervals of non-special heights. For example, if the special heights are 5 and 23, and N = 100, the intervals of non-special heights are [1 - 4], [6 - 22] and [24 - 100].
Now, for each query, a non-special height can only be visited outside the bucket, while the special ones can also be visited inside it. The idea behind the solution is to keep a partial mex for each interval of non-special heights, considering only the heights from (B + 1) * K to the right end of the query.
To be more precise, partialMex[x] will keep the smallest integer value greater then or equal to x that can't be found between the heights from (B + 1) * K to the current right end.
It is also important to notice that it is enough to calculate partialMex[x] only for the x$s at which an interval of non-special heights start. For the example above, $partialMex[x] is relevant only for x = 1, 6 or 24.
In order to keep these values properly, we will sort the queries (considered for the current bucket) by their right ends. The first queries will have their right ends inside the bucket, so we can iterate the heights in the query interval and calculate their mex in a brute-force manner, as we will make at most K steps.
The next queries will start to increase the right end, and we will mark the new heights as visited. Note that we only mark heights found outside the bucket in the visited bool array. Note, also, that we mark all heights, no matter they are special or not.
For each of the queries, we will calculate the answer the following way. We start with ans = 1 and try to increase it. At each step, ans represents a height which is either special or not. If it is special, increase ans if the height can be found in the bucket, after (to the right of) left end, or it is marked as visited, else stop and return ans. If it is not special, it means it belongs to some interval, and we should ask the corresponding partialMex how much can ans increase. If the partial mex tells us the hole interval has been seen, we can continue with our expansion with ans from 1 + right-end-of-the-interval. If we are stuck in the middle of the interval, it means the partial mex is the answer to the query. This way, we use exactly all the heights in the query interval.
The official implementation calculates partialMex[x] lazyly (not as we mark heights as visited, but as we need its value when answering a query). So, when we have some ans equal to the first non-special height of the current interval, we try to increase partialMex[ans] as long as we remain in a non-special interval of heights and as long as the value has been visited outside the bucket (marked in the visited bool array). Then we say ans = partialMex[ans] and move on.
To sum it up, for each bucket, as we move the right end along answering the queries, we keep track of the partial mex of each interval of non-special heights. This makes it possible that for each query we can see at most 2 * K + 1 values: the special heights and the K + 1 intervals, which we jump in constant time because of the partial mex we keep for each of them. Also, the partial mex for each interval can only increase interval-length times, giving a total of at most N steps for each bucket.
Let's analyze the complexity of the algorithm. For each bucket, we visit O(N) positions, because the highest right end of a query is N - 1. We also increase partialMex O(N) times. For each query, we make O(K) suplimentary steps to find out the answer. Therefore, the complexity is O(N * N / K + Q * K) which reaches its minimum when K equals N / sqrt(Q), giving a complexity of O(N * sqrt(Q) + Q).
However, the solution requires a sorting of the queries by their right ends for each bucket, so the final complexity is O(N * sqrt(Q) + Q * logQ)
O((N + Q) * logN)
We will process the queries offline, in increasing order of their right ends. As we move along the heights array and answer the queries, we need to remember, for each height, which was the rightmost position we encountered it in the array. Suppose we know these values. Then, for each query, we need to find out the highest value val such that all values from 1 to val - 1 have this position greater than or equal to the left end of the query.
We can use a segment tree over the values. More precisely, suppose we keep this array, rightMostPosition[x] with the meaning, what is the rightmost position where the height is x, encountered so far (up the right end of the current query). rightMostPosition[x] = -1 if there was no height equal to x so far. The segment tree will simply store the minimum over these values.
When we change the right end of the current query, we can simply notify the array rightMostPosition with the new values encountered. Every change in rghtMostPosition means O(\log N) changes in the segment tree. Therefore, we know how to update the segment tree, but how to find the mex with it?
We will binary search the answer, using the segment tree. Each node of the segment tree will tell us whether all values in the node's segment can be seen in the query interval. The condition is that segmentTree[node] to be greater than or equal to the left end of the query. Using this condition, we can binary search the answer while moving along the segment tree in O(logN).
The final time complexity of the solution is O((N + Q) * logN).
Request Notice
Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana. Multumim lui 
