4389. [Ynoi2019 模拟赛] Yuno loves sqrt technology II

【题目背景】

图片。

【题目描述】

给你一个长度为 $n$ 的序列，$m$ 次查询一个区间 $[l,r]$ 的逆序对数。

【输入格式】

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示序列。

加下来 $m$ 行每行两个整数 $[l,r]$ 表示查询区间。

【输出格式】

$m$ 行，一行一个整数表示答案。

【样例输入】

4 1
1 4 2 3
2 4

【样例输出】

2

【数据规模与约定】

$1\le n,m\le 10^5$。

【来源】

Ynoi2019 模拟赛。

我们已经有了 $O(n\log n)-O(1)$ 的方法。