Optimal Encoding
Contest: Codeforces Round 715 (Div. 1)
Difficulty rating: 3500
Tags: brute force, data structures

Touko's favorite sequence of numbers is a permutation $$$a_1, a_2, \dots, a_n$$$ of $$$1, 2, \dots, n$$$, and she wants some collection of permutations that are similar to her favorite permutation.

She has a collection of $$$q$$$ intervals of the form $$$[l_i, r_i]$$$ with $$$1 \le l_i \le r_i \le n$$$. To create permutations that are similar to her favorite permutation, she coined the following definition:

- A permutation $$$b_1, b_2, \dots, b_n$$$ allows an interval $$$[l', r']$$$ to holds its shape if for any pair of integers $$$(x, y)$$$ such that $$$l' \le x < y \le r'$$$, we have $$$b_x < b_y$$$ if and only if $$$a_x < a_y$$$.
- A permutation $$$b_1, b_2, \dots, b_n$$$ is $$$k$$$-similar if $$$b$$$ allows all intervals $$$[l_i, r_i]$$$ for all $$$1 \le i \le k$$$ to hold their shapes.

Yuu wants to figure out all $$$k$$$-similar permutations for Touko, but it turns out this is a very hard task; instead, Yuu will encode the set of all $$$k$$$-similar permutations with directed acylic graphs (DAG). Yuu also coined the following definitions for herself:

- A permutation $$$b_1, b_2, \dots, b_n$$$ satisfies a DAG $$$G'$$$ if for all edge $$$u \to v$$$ in $$$G'$$$, we must have $$$b_u < b_v$$$.
- A $$$k$$$-encoding is a DAG $$$G_k$$$ on the set of vertices $$$1, 2, \dots, n$$$ such that a permutation $$$b_1, b_2, \dots, b_n$$$ satisfies $$$G_k$$$ if and only if $$$b$$$ is $$$k$$$-similar.

Since Yuu is free today, she wants to figure out the minimum number of edges among all $$$k$$$-encodings for each $$$k$$$ from $$$1$$$ to $$$q$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 25\,000$$$, $$$1 \le q \le 100\,000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ which form a permutation of $$$1, 2, \dots, n$$$.

The $$$i$$$-th of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$. ($$$1 \le l_i \le r_i \le n$$$).

Output format:
Print $$$q$$$ lines. The $$$k$$$-th of them should contain a single integer  — The minimum number of edges among all $$$k$$$-encodings.

Constraints:
Time limit: 7.0 s
Memory limit: 1024.0 MB

Note:
For the first test case:

- All $$$1$$$-similar permutations must allow the interval $$$[1, 3]$$$ to hold its shape. Therefore, the set of all $$$1$$$-similar permutations is $$$\{[3, 4, 2, 1], [3, 4, 1, 2], [2, 4, 1, 3], [2, 3, 1, 4]\}$$$. The optimal encoding of these permutations is
- All $$$2$$$-similar permutations must allow the intervals $$$[1, 3]$$$ and $$$[2, 4]$$$ to hold their shapes. Therefore, the set of all $$$2$$$-similar permutations is $$$\{[3, 4, 1, 2], [2, 4, 1, 3]\}$$$. The optimal encoding of these permutations is
- All $$$3$$$-similar permutations must allow the intervals $$$[1, 3]$$$, $$$[2, 4]$$$, and $$$[1, 4]$$$ to hold their shapes. Therefore, the set of all $$$3$$$-similar permutations only includes $$$[2, 4, 1, 3]$$$. The optimal encoding of this permutation is

Example input:
4 3
2 4 1 3
1 3
2 4
1 4

Example output:
2
4
3

Example input:
8 4
3 7 4 8 1 5 2 6
3 6
1 6
3 8
1 8

Example output:
3
5
9
7

Editorial:
We will first solve the problem for $$$q$$$-similar permutations only. Let's transform each of the $$$q$$$ ranges into edges on a DAG we call $$$G$$$: for all ranges $$$[l_i, r_i]$$$, for all pairs of indices $$$l \le x, y \le r$$$ such that $$$a_x < a_y$$$, we add an edge from $$$x$$$ to $$$y$$$. We can easily see a permutation is $$$q$$$-similar iff it satisfies $$$G$$$. Now, our task is to remove edges from $$$G$$$ such that the number of permutations that satisfy it stays the same.
Lemma 1. We can remove an edge $$$(u, v)$$$ if and only if there is a path from $$$u$$$ to $$$v$$$ with length $$$\ge 2$$$.
Proof. If there exists a path of length $$$\ge 2$$$ between $$$(u, v)$$$, then we can remove the edge $$$(u, v)$$$ without having to worry about losing dependency between $$$u$$$ and $$$v$$$. On the other hand, if there doesn't exist such a path, then the only path connecting $$$u$$$ and $$$v$$$ is via the edge $$$(u, v)$$$ itself; removing that edge removes any dependency between $$$u$$$ and $$$v$$$. When that is the case, we can easily create a permutation such that $$$a_v = a_u + 1$$$, then we simply swap $$$a_u$$$ and $$$a_v$$$ to gain a permutation that does not satisfy the original DAG.
Let's return to our problem. For any element $$$u$$$, we consider the edges connecting $$$u \to v$$$ such that $$$v > u$$$ a right edge of $$$u$$$; we define a left edge of $$$u$$$ in a similar manner.
Lemma 2. There is at most one right edge of $$$u$$$.
Proof. Suppose there are two right edges of $$$u$$$, namely $$$u \to w'$$$ and $$$u \to w$$$ (suppose $$$w' < w$$$). Because of our range construction, there must be a range that covers both $$$u$$$ and $$$w$$$. This range must covers $$$w'$$$ too, therefore there is a path between $$$w$$$ and $$$w'$$$, therefore we can remove either $$$u \to w$$$ or $$$u \to w'$$$.
Therefore, there is at most one right edge $$$u \to u_r$$$. We can actually find this right edge: suppose $$$[l, r]$$$ is a range such that $$$l \le u \le r$$$, and $$$r$$$ is as large as possible. Then $$$u_r$$$ is the index between $$$u$$$ and $$$r$$$ such that $$$a_{u_r} > a_u$$$ and $$$a_{u_r}$$$ is as small as possible. We can prove similar results with the left edge of $$$u$$$ (denoted as $$$u \to u_l$$$).
However, there will be cases when $$$u \to u_r$$$ is actually not needed (I will call this phenomenon being hidden). What is the condition for $$$u \to u_r$$$ to be hidden? That's when there's a path from $$$u$$$ to $$$u_r$$$ with length $$$\ge 2$$$! Suppose this path is in the format $$$u \to \dots \to t \to u_r$$$. We can prove that $$$t < u$$$: if $$$t > u$$$ then that implies $$$a_t > a_u$$$ but $$$a_t < a_{u_r}$$$, which means the right edge of $$$u$$$ is $$$u \to t$$$ instead. Because $$$t < u$$$, we can take the range $$$[l, r]$$$ such that $$$l \le u_r \le r$$$, $$$l$$$ is as small as possible, and check if there exists an index $$$t \in [l, u]$$$ such that $$$a_u < a_t < a_w$$$. That concludes the solution for finding the optimal encoding for $$$q$$$-permutations. To recap:
1. Find left and right edges of all $$$u$$$.
2. Check if the left/right edges of all $$$u$$$ are hidden. If they are, remove them from the answer.
Let's return to the original problem. For each range $$$[l_i, r_i]$$$, instead of adding an edge for every $$$l \le x, y \le r$$$ to $$$G$$$, let's only add an edge between $$$x'$$$ and $$$y'$$$ such that $$$a_{x'}$$$ and $$$a_{y'}$$$ are adjacent values in the range. This doesn't change our answer because of lemma 1. Let's call these edges candidate edges.
Surprisingly, all of our previous observations hold, but this time on the set of candidate edges. Namely,
• At any query, there is at most one right edge $$$u \to u_r$$$, which is one of the candidate edges.
• The right edge $$$u \to u_r$$$ must satisfy that $$$u_r > u$$$, $$$a_{u_r} < a_u$$$ and $$$a_{u_r}$$$ is the smallest such value in the range $$$[u, r]$$$, where $$$[l, r]$$$ is the range covering $$$u$$$ with the largest $$$r$$$.
• $$$u \to u_r$$$ is hidden if there exists a candidate edge $$$u \to t$$$ such that $$$t < u$$$, $$$a_u < a_t < a_{u_r}$$$, and $$$t \in [l, u]$$$ where $$$[l, r]$$$ is the range covering $$$u_r$$$ with the smallest $$$l$$$. We call this edge $$$u \to t$$$ the destroyer of the edge $$$u \to u_r$$$.
• All of the above points holds for the left edge $$$u \to u_l$$$.
Let's organize the candidate edges: for any edge $$$u \to v$$$, if $$$v > u$$$, label $$$u \to v$$$ as a right candidate edge of $$$u$$$, else label $$$u$$$ as a left candidate edge of $$$u$$$. Let's sort the right candidate edges of $$$u$$$ by increasing $$$u_r$$$, and sort the left candidate edges of $$$u$$$ by decreasing $$$u_l$$$.
Observation. The values of the right end of the right candidate edges are decreasing, i.e. if the right candidate edges of $$$u$$$ are $$$u \to u_{r,1}, u \to u_{r,2}, ..., u \to u_{r,k}$$$ such that, $$$u_{r,1} < u_{r,2} < \dots < u_{r,k}$$$, then $$$a_{u_{r,1}} > a_{u_{r,2}} > \dots > a_{u_{r,k}}$$$. Similarly, if we sort the left candidate edges of $$$u$$$ by decreasing index, then the values of the left end of these candidate edges are decreasing.
Using this observation, we can prove that if the destroyer of $$$u \to u_{r_i}$$$ is $$$u \to u_{l_j}$$$, and the destroyer of $$$u \to u_{r_{i + 1}}$$$ is $$$u \to u \to u_{l, k}$$$, then $$$u_{l, j} \ge u_{l, k}$$$, or $$$j \le k$$$; we can also prove a similar result with the destroyers of left candidate edges. Therefore, we can use two pointers to figure out the destroyer for each left and right candidate edge of $$$u$$$.
For each right candidate edge $$$[u \to u_{r,i}]$$$, let's see when this candidate edge is used in the optimal encoding:
• The candidate edge is first activated when there exists a range covering $$$[u, u_{r, i}]$$$. We call this timestamp $$$t_1$$$.
• The candidate edge is hidden when there exists a range covering $$$[u_{l, j}, u_{r,i}]$$$, where $$$u \to u_{l,j}$$$ is the destroyer of $$$u \to u_{r,i}$$$. We call this timestamp $$$t_2$$$.
• The candidate edge is deactivated when there exists a range covering $$$[u, u_{r, i + 1}]$$$, where $$$u \to u_{r, i + 1}$$$ is the right candidate edge after $$$u \to u_{r,i}$$$. We call this timestamp $$$t_3$$$.
For each candidate edge, we can find these timestamps using a Fenwick tree. With these three timestamps, we can figure out the range of time where each candidate edge is used (which is $$$[t_1, \min(t_2, t_3))$$$), and modify the answer accordingly.
Finally, let's find out how many candidate edges there are:
Lemma 3. The number of candidate edges is $$$O(n \sqrt{q})$$$.
Proof. Suppose for a range $$$[l, r]$$$, we maintain edges $$$u \to v$$$ such that $$$l \le u, v \le r$$$, and the values $$$a_u$$$ and $$$a_v$$$ are adjacent in the range $$$[l, r]$$$. When we add/subtract one of the ends by 1, i.e. when we consider $$$[l \pm 1, r \pm 1]$$$, the amount of edges that are modified between $$$[l, r]$$$ and $$$[l \pm 1, r \pm 1]$$$ is $$$O(1)$$$ (for example, if we add another element, then we remove at most 1 old edge and add at most 2 new edges; similarly, when removing an element, we remove at most 2 old edges and add at most 1 new edge).
Therefore, consider Mo's algorithm on the given collection of ranges $$$[l_i, r_i]$$$, each candidate edge must appear during the process of iterating over the ranges, and the number of modification is $$$O(n \sqrt{q})$$$, therefore the number of candidate edges is $$$O(n \sqrt{q})$$$.
That concludes the solution to the full problem. To recap:
• Find all candidate edges.
• Find the destroyer of all candidate edges.
• Find the range of timestamps where each candidate edge is used.
The complexity is $$$O(n \sqrt{q} \log n)$$$.
Notes. In particular, your set candidate edges does not have to be exactly the edges connecting consecutive values between ranges; these candidate edges only need to satisfy 3 conditions:
• All edges that are included in some optimal $$$k$$$-encoding must be present in the set of candidate edges.
• The observation is not violated, i.e. if we sort the left/right candidate edges of any node $$$u$$$ by the other endpoint, then the value at the other endpoint must be sorted as well.
• The number of candidate edges must not be too large, at about $$$O(n \sqrt{q})$$$ edges.
This is to loosen up the process of generating the candidate edges, since the naive Mo-and-set-of-values approach is incredibly expensive. My edge-generating approach involves using Mo with rollback to only allow deletion of values so I can maintain the sorted values with a linked list, and I also do not delete intermediary edges while iterating one range to another.