P5047 [Ynoi2019 Mock Contest] Yuno loves sqrt technology II


You are given a sequence $a$ of length $n$ and $m$ queries. For each query, you need to find the number of inversion pairs in a given interval.

The first line contains two integers $n, m$. The second line contains $n$ integers representing the sequence. Then follow $m$ lines, each containing two integers representing the query interval.

Output $m$ lines, each with one integer representing the answer to the query.

$1 \leq n, m \leq 10^5$, $0 \leq a_i \leq 10^9$. We already have an algorithm faster than $n^{1.5}$. Source By nzhtl1477 Translated by ChatGPT 5