Inversion Pair
题目描述
对于一个序列 $p$,我们定义:$p$ 中的逆序对个数为 $\mathrm{W}(p)$。
注:这里的逆序对即为满足 $p_i>p_j$ 且 $i<j$ 的一对数。
现在,给定一个序列 $a$,其为整数 $1\sim n$ 的排列。也就是说,对于任意的 $1\le i\le n$,都有 $1\le a_i\le n$,$a_i$ 均为整数且互不相同。
现有一张图,上有 $n$ 个节点,编号为整数 $1\sim n$。对于任意的两个编号为 $i,j(1\le i< j\le n)$ 的节点,我们将在它们之间连一条权值为 $\mathrm{W}([a_i,a_{i+1},\dots,a_{j-1},a_j])$ 的无向边。
现有 $q$ 次询问。每次询问给出两个编号为 $x,y$ 节点,求它们之间的最短路径。
输入输出格式
输入格式
第一行两个整数 $n,q$。
第二行 $n$ 整数表示序列 $a$。
接下来 $q$ 行,每行两个整数表示一次询问的 $x,y$。
输出格式
对于每一次询问:
一个整数表示所求的最短路径。
输入输出样例
输入样例 #1
3 2
3 1 2
1 3
2 2
输出样例 #1
1
0
说明
对于全部数据,保证:$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$ | 分数 | 特殊性质 |
|:-:|:-:|:-:|:-:|:-:|
| $0$ | $100$ | $100$ | $30$ | 无 |
| $1$ | $3\times 10^5$ | $3\times 10^5$ | $70$ | 无 |