P11015 Inversion Pair

对于一个序列 $p$，我们定义：$p$ 中的逆序对个数为 $\mathrm{W}(p)$。 注：这里的逆序对即为满足 $p_i>p_j$ 且 $i

第一行两个整数 $n,q$。 第二行 $n$ 整数表示序列 $a$。 接下来 $q$ 行，每行两个整数表示一次询问的 $x,y$。

对于每一次询问： 一个整数表示所求的最短路径。

对于全部数据，保证：$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$ | 无 |