652B - z-sort
The problem was suggested by Smaug.
Easy to see that we can z-sort any array a. Let be the number of even positions in a. We can assign to those positions k maximal elements and distribute other n - k elements to odd positions. Obviously the resulting array is z-sorted.
Complexity: O(nlogn).
652C - Foe Pairs
This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.
Let's precompute for each value x its position in permutation posx. It's easy to do in linear time. Consider some foe pair (a, b) (we may assume posa < posb). Let's store for each value a the leftmost position posb such that (a, b) is a foe pair. Denote that value as za. Now let's iterate over the array a from right to left and maintain the position rg of the maximal correct interval with the left end in the current position lf. To maintain the value rg we should simply take the minimum with the value z[lf]: rg = min(rg, z[lf]). And finally we should increment the answer by the value rg - lf + 1.
Complexity: O(n).
652D - Nested Segments
The problem was suggested by Alexey Dergunov dalex.
This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each i we should count the number of indices j so that the following conditions are hold: ai < aj and bj < aj. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment.
So the condition ai < aj is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition bj < bj is hold by taking the prefix sum in data structure (the second dimension).
Complexity: O(nlogn).