4388. [Ynoi2019 模拟赛] Yuno loves sqrt technology I

【题目背景】

图片。

【题目描述】

给定一个长度为 $n$ 的排列，$m$ 次查询，每次查询一个区间的逆序对数，强制在线。

【输入格式】

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

第二行 $n$ 个正整数表示这个排列。

之后 $m$ 行，每行两个整数表示查询的区间。

本题强制在线，每次查询输入的数要 xor 上上次答案，第一次询问视上次答案为 $0$。

【输出格式】

输出 $m$ 行，每行一个数表示这次询问的答案

【样例输入】

4 1
1 4 2 3
2 4

【样例输出】

2

【数据规模与约定】

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

注意：本题因为评测机缘故，短时间内的大量提交会影响程序运行效率，且数据难以区分正解和错解。

【来源】

Ynoi2019 模拟赛。

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