给你一个长为 \(n\) 的排列,\(m\) 次询问,每次查询一个区间的逆序对数,强制在线。
\(1 \leq n,m\leq 10^5\),时限 \(750\text{ms}\),空限 \(500\text{MB}\)。
静态查询逆序对数。
根据这题没有修改,容易想到直接预处理,\(\mathcal O(\sqrt{n})\) 内回答询问即可。
考虑序列分块。
预处理方法一
类似于归并排序,需要预处理的信息有:
对于 \(1,2\),用树状数组扫一遍即可,单块时间复杂度为 \(\mathcal O(\sqrt n \log \sqrt n)\),总时间复杂度为 \(\mathcal O(n \log \sqrt n)\),可过。
对于 \(3\),设其为 \(f[i][j]\),则有递推公式:
\[f[i][j]=f[i][j-1]+f[i+1][j]-f[i+1][j-1]+(\ i \ \text{所在块和}\ j \ \text{所在块产生的贡献}) \]时间复杂度为 \(\mathcal O(n \sqrt n)\),可过。
对于 \(4\),对于每一个 \(j\),先在每一个块内扫一遍,再计算前缀和即可,时间复杂度为 \(\mathcal O(n \sqrt n)\),可过。
预处理好了,接下来考虑怎么查询,对于一个询问 \(l,r\):
若 \(l,r\) 在同一块内,则答案为块首到 \(r\) 的贡献和块首到 \(l-1\) 的贡献之差,内部贡献用 \(1\) 计算,两块贡献用归并求即可。
若 \(l,r\) 不在同一块内,则分成两个散块和多个整块,先用 \(3\) 计算好整块的内部贡献,然后根据 \(4\) 求散块与整块的贡献,再归并求散块对散块的贡献,最后散块内部贡献用上面那种方法计算即可。
总时间复杂度为 \(\mathcal O((n+m)\sqrt{n})\),总空间复杂度为 \(\mathcal O(n \sqrt n)\)。
预处理方法二
记 \(F[i][j]\) 表示 \([l,r]\) 这段区间与第 \(j\) 块中的数产生的逆序对数,记为 \(5\)。
再把法一中的 \(1,2,3\) 照搬过来。
考虑计算 \(F\),对于每个块,对于每个块,归并记录每个数对块的贡献,然后算一遍前缀和即可,时间复杂度 \(\mathcal O(n \sqrt n)\),可过。
这样计算 \(f\) 的时候可以省掉一个 \(\mathcal O(\sqrt n)\) 的归并。
对于询问 \(l,r\):
总时间复杂度为 \(\mathcal O((n+m)\sqrt{n})\),总空间复杂度为 \(\mathcal O(n \sqrt n)\),但常数较法一更为优秀。
\(\text{01-31 / 21:29:13 / 2.91s / 132.38MB / 4.00KB C++98 O2}\)。
#include <cstdio> #include <algorithm> namespace Fread { const int SIZE = 1 << 23; char buf[SIZE], *S, *T; inline char getchar() { if (S == T) { T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n'; } return *S++; } } namespace Fwrite { const int SIZE = 1 << 23; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() { fwrite(buf, 1, S - buf, stdout); S = buf; } inline void putchar(char c) { *S++ = c; if (S == T) flush(); } struct NTR { ~NTR() { flush(); } } ztr; } #ifdef ONLINE_JUDGE #define getchar Fread::getchar #define putchar Fwrite::putchar #endif inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } inline void write(long long x) { if(x < 0) { putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } const int _ = 1e5 + 7, M = 320, siz = 317; int n, m, a[_], L[M], R[M], bel[_], blo, pre[_], suf[_], f[M][_]; long long F[M][M], ans; int x[M], y[M], lx, ly, c[_], d[_]; struct Pair { int fi, se; inline bool operator < (const Pair & tmp) const { return fi < tmp.fi; } } b[_]; struct BIT { int b[_]; inline void add(int x, int val) { for(int i = x; i < _; i += i & -i) b[i] += val; } inline int ask(int x) { int res = 0; for(int i = x; i; i -= i & -i) res += b[i]; return res; } } t; inline int merge(int *a, int *b, int la, int lb) { int ia = 1, ib = 1, res = 0; while(ia <= la && ib <= lb) if(a[ia] < b[ib]) ++ia; else { res += la - ia + 1; ++ib; } return res; } inline void init() { blo = (n - 1) / siz + 1; for(int i = 1; i <= blo; ++i) { L[i] = R[i - 1] + 1; R[i] = i * siz; } R[blo] = n; for(int i = 1; i <= n; ++i) b[i] = (Pair) { a[i], i }; for(int i = 1; i <= blo; ++i) { std::sort(b + L[i], b + R[i] + 1); for(int j = L[i]; j <= R[i]; ++j) { bel[j] = i; c[j] = b[j].fi; d[j] = b[j].se; } int x = 0; for(int j = L[i]; j <= R[i]; ++j) { t.add(a[j], 1); x += t.ask(n) - t.ask(a[j]); pre[j] = x; } F[i][i] = x; for(int j = L[i]; j <= R[i]; ++j) { suf[j] = x; t.add(a[j], -1); x -= t.ask(a[j] - 1); } } std::sort(b + 1, b + n + 1); for(int j = 1; j <= blo; ++j) for(int i = 1, k = L[j]; i <= n; ++i) { const int id = b[i].se; while(k <= R[j] && b[i].fi > c[k]) ++k; if(id < L[j]) f[j][id] = k - L[j]; else if(id > R[j]) f[j][id] = R[j] - k - (k <= R[j] && b[i].fi == c[k]) + 1; } for(int i = 1; i <= blo; ++i) for(int j = 2; j <= n; ++j) f[i][j] += f[i][j - 1]; for(int len = 1; len <= blo; ++len) for(int i = 1; i <= blo; ++i) { if(len + i > blo) break; const int j = i + len; F[i][j] = F[i + 1][j] + F[i][j - 1] - F[i + 1][j - 1] + f[j][R[i]] - f[j][L[i] - 1]; } } signed main() { n = read(), m = read(); for(int i = 1; i <= n; ++i) a[i] = read(); init(); while(m--) { int l = read() ^ ans, r = read() ^ ans, bl = bel[l], br = bel[r]; lx = ly = 0; if(bl == br) { for(int i = L[bl]; i <= R[bl]; ++i) { if(l <= d[i] && d[i] <= r) y[++ly] = c[i]; else if(d[i] < l) x[++lx] = c[i]; ans = pre[r] - ((l == L[bl]) ? 0 : pre[l - 1]) - merge(x, y, lx, ly); } } else { ans = F[bl + 1][br - 1] + pre[r] + suf[l]; for(int i = bl + 1; i <= br - 1; ++i) ans += f[i][R[bl]] - f[i][l - 1] + f[i][r] - f[i][L[br] - 1]; for(int i = L[bl]; i <= R[bl]; ++i) if(d[i] >= l) x[++lx] = c[i]; for(int i = L[br]; i <= R[br]; ++i) if(d[i] <= r) y[++ly] = c[i]; ans += merge(x, y, lx, ly); } write(ans), putchar('\n'); } }