A monotonic week

The Mar 9 - Mar 15 week was light on contests, so let's come back to the Codeforces problem from the previous summary: you are given a sequence of at most 500000 numbers. In one step, you simultaneously replace every number except the first one and the last one with the median of the following set: this number itself, the number on the left, and the number on the right. For example, if you start with 3 1 4 2 5, then after one step you get 3 3 2 4 5, after two steps it becomes 3 3 3 4 5, and then it does not change anymore. What will be the stable state of the sequence, and how many steps are needed to reach it?

Since I did not solve the problem myself, I will describe the solution from the tutorial. First, let's assume that the input sequence has only numbers 1 and 2. Then the process is somewhat straightforward: if there are two or more adjacent numbers that are equal, they will never change; and for each maximal subsegment of alternating numbers, at every step all numbers in it except the first and the last one will flip from 1 to 2 and vice versa, thus reducing the length of the alternating sequence by 2, until it eventually disappears: 12121212 -> 11212122 -> 11121222 -> 11112222 -> 11112222 -> ...

Here comes the most beautiful part of the solution: we can notice that the process is in some sense monotonic. More specifically, if we take the input sequence, replace all numbers that are less than or equal to some boundary b by 1, and all numbers greater than b by 2, then run the process on this sequence of 1s and 2s in parallel to the process on the original sequence, then the relation between them will always stay the same: after any number of steps, all numbers less than or equal to b in the first sequence will correspond to 1s in the second sequence. Since we know how to find the stable state for the sequence of 1s and 2s, we know which numbers in the stable state of the original sequence are less than or equal to b, and which are greater than b!

Since we also know that all numbers in the stable state are equal to some number of the original sequence, doing the above process for all values of b equal to some number of the original sequence allows us to reconstruct the steady state: every number can be determined as the lowest value of b for which it corresponded to a 1.

When implemented naively, this solution would be quadratic which is not good enough. However, we can process the values of b in increasing order, and maintain a set of all alternating sequences of 1s and 2s in the second sequence in a balanced tree. We have n events, in each of those one of the 2s becomes a 1, and in each event at most two alternating sequences adjacent to the place of modification will be affected. The balanced tree allows to find, add and remove those in logarithmic time, therefore we can simulate the entire process in O(n*logn). And in order to construct the answer, we can maintain the set of positions which still have a 2 in the steady state in another balanced tree, and remove appropriate positions from it whenever a new alternating sequence appears, since each alternating sequence produces at most one segment of consecutive 1s in the steady state, which ends up being amortized O(n*logn) as well.

Thanks for reading, and check back for more!