P5046 [Ynoi2019 Mock Contest] Yuno loves sqrt technology I


You are given a **permutation** of length $n$ and $m$ queries. Each query asks for the number of inversion pairs in a subarray interval, and the queries must be answered online.

The first line contains two integers $n, m$. The second line contains $n$ positive integers representing this **permutation**. The next $m$ lines each contain two integers representing the query interval. This problem is strictly online: for each query, the input numbers must be xor-ed with $lastans$. For the first query, $lastans = 0$ by default.

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

$1 \le n, m \le 10^5$. We already have an online algorithm with time complexity below $n^{1.5}$. Source: By nzhtl1477. Translated by ChatGPT 5