P11015 Inversion Pair

.

For a sequence $p$, we define $\mathrm{W}(p)$ as the number of inversion pairs in $p$. Note: An inversion pair here means a pair that satisfies $p_i > p_j$ and $i < j$. Now you are given a sequence $a$, which is a permutation of the integers $1 \sim n$. That is, for any $1 \le i \le n$, we have $1 \le a_i \le n$, all $a_i$ are integers, and they are all distinct. There is a graph with $n$ nodes, numbered $1 \sim n$. For any two nodes with indices $i, j \ (1 \le i < j \le n)$, we add an undirected edge between them with weight $\mathrm{W}([a_i, a_{i+1}, \dots, a_{j-1}, a_j])$. There are $q$ queries. Each query gives two nodes numbered $x, y$, and you need to find the shortest path between them.

The first line contains two integers $n, q$. The second line contains $n$ integers representing the sequence $a$. The next $q$ lines each contain two integers, representing one query $x, y$.

For each query: Output one integer, the length of the required shortest path.

For all testdata, it is guaranteed that: $2 \le n \le 3 \times 10^5$, $1 \le q \le 3 \times 10^5$, $1 \le x, y \le n$. | $\text{Subtask}$ | $n \le$ | $q \le$ | Score | Special Property | |:-:|:-:|:-:|:-:|:-:| | $0$ | $100$ | $100$ | $30$ | None | | $1$ | $3 \times 10^5$ | $3 \times 10^5$ | $70$ | None | Translated by ChatGPT 5