PROBLEM LINK:
Contest  Division 3
Contest  Division 2
Contest  Division 1
DIFFICULTY:
EASYMEDIUM
PROBLEM:
Given a permutation array A of size N. Determine the number of ranges [L, R] such that, after erasing all elements A_i where
 i\notin [L,R] or,
 A_i\notin [L,R],
the resultant array is sorted.
EXPLANATION:
Definition: Call a rangearray valid, if its elements are sorted in increasing order.
Claim: If the rangearray of [L, R] is valid, then the rangearray of [L',R'] is also valid, for all L\le L' \le R'\le R.
Proof
Consider a sequence of steps that changes [L, R] to [L',R'] by reducing the size of the range in each step (increasing L or decreasing R by 1).
In each step, elements from the initial rangearray are deleted to create the rangearray of the new range, and it is easy to see that no new elements are added to the rangearray.
Therefore, since the rangearray of [L, R] is sorted, deleting any number of elements from it (while preserving the order) still keeps it sorted, implying the rangearray of [L',R'] is sorted and thus valid.
For each r, let us calculate the number of ranges [l, r] whose rangearray is valid. Then, the answer is equal to the sum of the number of ranges, over all r. More formally, if v_r is the smallest value such that rangearray [v_r, r] is valid, the answer to the problem is equal to:
From the initial claim, it is clear that v_i \le v_j for all i<j. This little observation allows us to calculate array v in an increasing fashion efficiently, using a modified twopointer approach.
Implementation
Let L and R be the bounds of the range we are currently considering. Also, let S be the rangearray of [L,R]. Initially, L=R=1.
Iterate R from 1 to N. In each iteration, do the following.
First, update S to reflect the rangearray of the new range [L,R] (recall that S is currently equal to the range array of [L, R1]).
How?
If you observe the rangearray of [L, R1] and [L, R], the only new elements (there are no deletions) in the range array of the latter range are:
 element A_R, only if L\le A_R\le R holds, and
 element R, only if L\le pos_R \le R1 holds (where pos_x is the position index of element x in A).
(The case work required to arrive at the above conclusion is trivial and left to the reader as an exercise.)
Insert the necessary values at their corresponding positions in S to get the new rangearray of [L, R] (how to do this is explained later, bear with me).
Then, while S is not sorted, increase the value of L by 1 and recompute the rangearray of the new range.
How?
Similar to the previous spoiler, the only deletions in the rangearray of [L,R] to get the rangearray of [L+1, R] are:
 element A_L, only if L\le A_L\le R holds, and
 element L, only if L+1\le pos_L \le R holds.
It is easy to deduce that the value of L at the end of the two steps in each iteration is equal to v_R.
To compute S efficiently in each step, we can use an ordered set of pairs, sorted by the first term (std::set<pair<int, int>>
in C++).

To insert element A_i in its corresponding position in the rangearray, we can insert pair (i, A_i) into S.

We can similarly remove element A_i by erasing (i, A_i) from S.

Everytime we insert into S, we can check if the rangearray is still sorted by comparing the second value of the inserted pair with itâ€™s left and right neighbours in S (If S is no longer sorted after an insertion, we keep increasing L, removing elements in the process, until S is sorted again).
Each of the above operations takes O(\log S).
TIME COMPLEXITY:
(Refer implementation spoiler for terminologies).
Since each element of A is inserted and removed from S at most once, and since each operation on S has complexity O(\log S), the total time complexity per test case is
SOLUTIONS:
Editorialistâ€™s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
 1
 2
 3
 4
 5
0 voters