P5046 Yuno loves sqrt technology I
给你一个长为 \(n\) 的排列，\(m\) 次询问，每次查询一个区间的逆序对数，强制在线。
\(1 \leq n,m\leq 10^5\)，时限 \(750\text{ms}\)，空限 \(500\text{MB}\)。
sol
静态查询逆序对数。
根据这题没有修改，容易想到直接预处理，\(\mathcal O(\sqrt{n})\) 内回答询问即可。
考虑序列分块。
预处理方法一
类似于归并排序，需要预处理的信息有：
- 每个元素到其块首这段区间的逆序对数。
- 每个元素到其块尾这段区间的逆序对数。
- 块 \(i\) 到块 \(j\) 这段区间的逆序对数。
- 前 \(i\) 个块中，小于等于 \(j\) 的元素个数。
对于 \(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\)：
- 若 \(l,r\) 在同一块内，则答案为块首到 \(r\) 的贡献和块首到 \(l-1\) 的贡献之差，内部贡献用 \(1\) 计算，两块贡献用归并求即可。
- 若 \(l,r\) 不在同一块内，则分成两个散块和多个整块，先用 \(3\) 计算好整块的内部贡献，然后根据 \(5\) 差分求散块与整块的贡献，再归并求散块对散块的贡献，最后散块内部贡献用上面那种方法计算即可。
总时间复杂度为 \(\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');
}
}