Sorting Problem Again
Contest: Codeforces Round 955 (Div. 2, with prizes from NEAR!)
Difficulty rating: 2600
Tags: binary search, data structures, sortings

You have an array $$$a$$$ of $$$n$$$ elements. There are also $$$q$$$ modifications of the array. Before the first modification and after each modification, you would like to know the following:

What is the minimum length subarray that needs to be sorted in non-decreasing order in order for the array $$$a$$$ to be completely sorted in non-decreasing order?

More formally, you want to select a subarray of the array $$$(l, r)$$$ with the minimum value of $$$r - l + 1$$$. After that, you will sort the elements $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$ and want the condition $$$a_{i} \le a_{i + 1}$$$ to hold for all $$$1 \le i < n$$$. If the array is already sorted in non-decreasing order, then $$$l$$$ and $$$r$$$ should be considered as equal to $$$-1$$$.

Note that finding such $$$(l, r)$$$ does not change the array in any way. The modifications themselves take the form: assign $$$a_{pos} = x$$$ for given $$$pos$$$ and $$$x$$$.

Input format:
Each test consists of several test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then follows the description of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$).

The second line of each test case contains $$$n$$$ integers $$$a_{i}$$$ ($$$0 \le |a_{i}| \le 10^{9}$$$) — the initial elements of the array $$$a$$$.

The third line of each test case contains a number $$$q$$$ ($$$0 \le q \le 5 \cdot 10^{5}$$$) — the number of modifications to the array.

The following $$$q$$$ lines of each test case contain two integers $$$pos_{i}$$$ ($$$1 \le pos_{i} \le n$$$) and $$$val_{i}$$$ ($$$0 \le |val_{i}| \le 10^{9}$$$) — this means that for the $$$i$$$-th modification, $$$a_{pos_{i}}$$$ is assigned the value $$$val_{i}$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ for all test cases does not exceed $$$5 \cdot 10^{5}$$$.

Output format:
For each test case, output $$$q + 1$$$ lines. Each line should contain $$$2$$$ integers $$$l, r$$$ — the boundaries of the minimum subarray, such that sorting it will make the array $$$a$$$ completely sorted. If $$$a$$$ is already sorted, then output $$$l = -1$$$, $$$r = -1$$$.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
Let's consider the first test case:

- Initially, the array is sorted in non-decreasing order: $$$[2, 2, 3, 4, 5]$$$
- After the first query, the array looks like this: $$$[\color{red}{2}, \color{red}{1}, 3, 4, 5]$$$.
- After the second query, the array looks like this: $$$[\color{red}{2}, \color{red}{1}, \color{red}{3}, \color{red}{1}, 5]$$$.
- After the third query, the array looks like this: $$$[1, 1, \color{red}{3}, \color{red}{1}, 5]$$$.

The red segments indicate the subarrays that need to be sorted in order for the entire array to be sorted in non-decreasing order.

Example input:
2
5
2 2 3 4 5
3
2 1
4 1
1 1
5
1 2 3 4 5
9
1 4
2 3
5 2
3 1
1 1
5 1
4 1
3 1
2 1

Example output:
-1 -1
1 2
1 4
3 4
-1 -1
1 3
1 3
1 5
1 5
2 5
2 5
2 5
2 5
-1 -1

Editorial:
Let's maintain a set $$$s$$$ of positions $$$i$$$ such that $$$a_{i} < a_{i - 1}$$$, and also a segment tree (or any other data structure that allows changing the value at a position and finding the minimum/maximum on a segment). Recalculating the set and the segment tree is quite simple for each change in the array $$$a$$$.
To answer a query, let's notice a few facts:
• If $$$s$$$ is empty, then the array $$$a$$$ is completely sorted.
• If $$$s$$$ is not empty, then we can find the minimum and maximum elements from this set, denote them as $$$pos_{min}$$$, $$$pos_{max}$$$. With these elements, we can easily answer queries. Similarly to the previous point, we can say that the prefix of size $$$pos_{min}$$$ and the suffix of size $$$n - 1 - pos_{max}$$$ are sorted in non-decreasing order.
Now, at the very least, we need to sort the segment $$$(l, r)$$$ such that $$$l \le pos_{min}$$$, $$$r > pos_{max}$$$. How can we find exactly these $$$l$$$ and $$$r$$$? First, let's find $$$l$$$. To do this, we find the minimum on the segment $$$(pos_{min} - 1, pos_{max})$$$, this value will be somewhere in the prefix of the entire array, so we need to find the position in the prefix between which elements it should be inserted. But we also know that the prefix is sorted, so we can use binary search (as in insertion sort) and find the position for this value. This position will be our $$$l$$$.
For $$$r$$$, everything is similar, we find the maximum on the segment $$$(pos_{min} - 1, pos_{max})$$$ and also find its position in the sorted suffix.
In conclusion, to find the answer after changing the array, we need to find the maximum/minimum positions in $$$s$$$, the maximum/minimum on the segment, and perform $$$2$$$ binary searches on the prefix and suffix. All of this works in $$$O(\log n)$$$.
Complexity: $$$O((n + q) \cdot \log n)$$$
It is also worth noting that some solutions with $$$O((n + q) \cdot \log^{2} n)$$$ can also fit within the time limit if they are very carefully written and use a non-recursive segment tree.