「Ynoi2019 模拟赛」Yuno loves sqrt technology I

2026/8/10 21:40:32

这种比较难搞的往根号数据结构想。

维护以下几个东西

$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;
}