这种比较难搞的往根号数据结构想。
维护以下几个东西
- \(cnt_{i, j}\)：前 \(i\) 个块，\(\leq j\) 的元素个数。
- \(f_{i, j}\)：第 \(i\) 到第 \(j\) 个块构成的序列的逆序对个数。
- \(pre_i, suf_i\)：从下标 \(i\) 到所在块的左端点 \(/\) 右端点构成的序列的逆序对个数
假设我们已经维护好了，考虑怎么处理查询。答案可以被拆成整块构成的序列、两边散块与整块之间、两个散块之间的逆序对数量之和，对于整块构成的序列的逆序对数量我们已经预处理好了，两边散块与整块之间的逆序对数量我们可以暴力遍历散块元素 \(a_j\)（以 \(j\) 在右侧散块举例），设两边散块编号分别为 \(s, t\)，则查询 \(cnt_{t - 1, a_j} - cnt{s, a_j}\) 之和即是逆序对数量。
对于两个散块之间逆序对数量，我们可以在预处理时新开数组先对每个块内元素排好序得到数组 \(b\) 并记录 \(id_{a_i} = i\)，然后分别对两个散块按排序后顺序遍历 \(b_j\)，若 \(id_{b_j}\) 在查询区间内则将其加入 \(c/d\) 数组，之后 \(O(Siz)\) 归并即可，查询时间 \(O(M\sqrt{N})\)。
现在回过头想预处理，\(cnt\) 数组二位前缀和容易解决，\(pre, suf\) 在块内正着做一遍逆序对数量反着做一遍逆序对数量即可，\(f\) 稍微难想些，用一个小容斥，$f_{i, j} = f_{i, j - 1} + f_{i + 1, j} - f_{i + 1, j - 1} + $ 块 \(i\) 与块 \(j\) 之间逆序对数量，也是提前排序 \(O(\sqrt{N})\) 归并求，总体枚举 \(i, j\)，花费 \(O(\sqrt{N})\) 归并，预处理时间 \(O(N\sqrt{N})\)。
吐槽：我做法有点卡常，随便加了点卡常和快读，拆了个函数，交了两遍才过，最大点差 \(3 \text{ms} \ \text{TLE}\)。
时间复杂度 \(O((N + M) \sqrt{N})\)，空间复杂度 \(O(N \sqrt{N})\)。
/*
address:https://www.luogu.com.cn/problem/P5046
AC 2026/8/9 17:22
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const int S = 175;
int n, q;
int a[N], b[N], id[N];
int cnt[N / S + 5][N];
LL f[N / S + 5][N / S + 5];
int pre[N], suf[N];
int siz, blk;
int L[N / S + 5], R[N / S + 5], bel[N];
struct BinaryTree {
#define lowbit(x) (x & -x)int c[N];inline void clean(int x) { for (;x <= n;x += lowbit(x)) c[x] = 0; }inline void change(int x) { for (;x <= n;x += lowbit(x)) ++c[x]; }inline int query(int x) {int ret = 0;for (;x > 0;x -= lowbit(x)) ret += c[x];return ret;}
}BIT;
inline void init() {for (register int i = 1;i <= blk;++i) sort(b + L[i], b + R[i] + 1);for (register int i = 1;i <= blk;++i) {for (register int j = L[i];j <= R[i];++j) {f[i][i] += j - L[i] - BIT.query(a[j]);pre[j] = f[i][i];BIT.change(a[j]);}for (register int j = L[i];j <= R[i];++j) BIT.clean(a[j]);for (register int j = R[i];j >= L[i];--j) {suf[j] = suf[j + 1] + BIT.query(a[j]);BIT.change(a[j]);}for (register int j = L[i];j <= R[i];++j) BIT.clean(a[j]);}for (register int i = blk - 1;i >= 1;--i)for (register int j = i + 1;j <= blk;++j) {f[i][j] = f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1];for (register int x = L[i], y = L[j];x <= R[i];++x) {while (y <= R[j] && b[y] < b[x]) ++y;f[i][j] += y - L[j];}}for (register int i = 1;i <= blk;++i) {for (register int j = L[i];j <= R[i];++j) ++cnt[i][a[j]];for (register int j = 1;j <= n;++j) cnt[i][j] += cnt[i][j - 1] + cnt[i - 1][j] - cnt[i - 1][j - 1];}
}
LL lastans;
inline void read(int& x) {x = 0;char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
inline void read(LL& x) {x = 0;char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
int main() {read(n), read(q);for (register int i = 1;i <= n;++i) read(a[i]), b[i] = a[i], id[a[i]] = i;siz = max(1, int(sqrt(n) / 1.8)), blk = (n + siz - 1) / siz;for (register int i = 1;i <= n;++i) bel[i] = (i + siz - 1) / siz;for (register int i = 1;i <= blk;++i) L[i] = (i - 1) * siz + 1, R[i] = min(i * siz, n);init();while (q--) {LL l, r;read(l), read(r);l ^= lastans, r ^= lastans;const int s = bel[l], t = bel[r];if (s + 1 <= t - 1) lastans = f[s + 1][t - 1];else lastans = 0;int c[S + 5], d[S + 5];if (s == t) {int h = 0, w = 0;for (register int i = L[s];i <= R[s];++i)if (id[b[i]] < l) c[++h] = b[i];else if (id[b[i]] <= r) d[++w] = b[i];lastans = pre[r] - (l == L[s] ? 0 : pre[l - 1]);for (register int i = 1, j = 1;i <= h;++i) {while (j <= w && d[j] < c[i]) ++j;lastans -= j - 1;}}else {int h = 0, w = 0;for (register int i = L[s];i <= R[s];++i)if (id[b[i]] >= l) c[++h] = b[i];for (register int i = L[t];i <= R[t];++i)if (id[b[i]] <= r) d[++w] = b[i];lastans += pre[r] + suf[l];for (register int i = 1, j = 1;i <= h;++i) {while (j <= w && d[j] < c[i]) ++j;lastans += j - 1;}for (register int i = l;i <= R[s];++i) lastans += cnt[t - 1][a[i]] - cnt[s][a[i]];for (register int i = L[t];i <= r;++i) lastans += L[t] - R[s] - 1 - (cnt[t - 1][a[i]] - cnt[s][a[i]]);}printf("%lld\n", lastans);}return 0;
}