静态区间逆序对查询（Static Range Inversions Query）

问题描述

给定一个长度为 $N$ 的整数序列 $A_0, A_1, \dots, A_{N-1}$。
处理 $Q$ 个查询：对每个查询 l_i r_i，输出子数组 $(A_{l_i}, A_{l_i+1}, \dots, A_{r_i-1})$ 中的逆序对数量。

逆序对定义为：下标对 $(i, j)$ 满足 $l_i \le i < j < r_i$ 且 $A_i > A_j$。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq A_i \leq 10^9$
• $0 \leq l_i < r_i \leq N$

输入

$N\ Q$
$A_0\ A_1\ \cdots\ A_{N-1}$
$l_0\ r_0$
$l_1\ r_1$
:
$l_{Q-1}\ r_{Q-1}$

4 2
4 1 4 0
1 3
0 4

0
4