题解 P5046 【[Ynoi2019模拟赛]Yuno loves sqrt technology I】
诗乃
2019-10-31 22:34:09
分享一个思路较简单但容易被卡空间的算法。
预处理以下几个东西：
1、$ansL_{i,j}$，表示以$j$为左端点，第i块的右端点为右端点的区间中的逆序对数。
2、$ansR_{i,j}$，表示以$j$为右端点，第i块的左端点为左端点的区间中的逆序对数。
3、$ans_{l,r}$，表示以第$l$块的左端点为左端点，第$r$块的右端点为右端点的区间中的逆序对数。
那么对于每次询问我们只需要把1+2-3，就可以得到答案了。
——好像漏了啥。左散块对右散块的贡献没有统计。将所有块事先排好序，查询时归并一下即可。
如何预处理？
预处理出$cnt_{i,j}$为前$i$块大于/小于等于j的数字个数，$pre_i$为位置$i$到$i$所在块左端点中大于/小于等于$a_i$的数字个数，即可做到$O(1)$移动端点。
关于第三个$ans_{l,r}$，不难发现在处理前两个值的时候已经顺便求出来了，不需要做更多处理。
查询时若l,r在同一个块中，简单容斥一下即可。这个部分其他题解已经说明得非常清楚了不再赘述。
总复杂度$O(n\sqrt{n})$。
```cpp
#include <bits/stdc++.h>
#define bl(x) (((x)-1)/siz+1)
#define L(x) (((x)-1)*siz+1)
#define R(x) std::min(1ll*(x)*siz, 1ll*n)
using namespace std; typedef long long lint;
const int MAXN = 100050, MAXB = 205;
namespace fastIO {
const int buffer_size = 1024 * 1024 * 40;
char input[buffer_size], output[buffer_size];
char *fin, *fout;
inline void init() {
fread(input, 1, buffer_size, stdin);
fin = input; fout = output;
}
inline void flush() {
fwrite(output, 1, fout - output, stdout);
fflush(stdout);
}
inline int read(int u = 0, char c = *fin++, bool f = false) {
for (;!isdigit(c); c = *fin++) f |= c == '-';
for (; isdigit(c); c = *fin++) u = u * 10 + c - '0';
return f ? -u : u;
}
inline void read(char *s, char c = *fin++) {
for (;!isspace(c); c = *fin++);
for (; isspace(c); c = *fin++) *s++ = c;
*s = '\0';
}
inline void print(lint u) {
u < 0 ?
*fout++ = '-', print(-u) :
void(u > 9 ?
print(u / 10), *fout++ = u % 10 + '0' :
*fout++ = u + '0');
}
inline void print(char *s) { while (*s) *fout++ = *s++; }
inline void print(char c) { *fout++ = c; }
}
using fastIO::read; using fastIO::print;
int P[MAXN], cx, cy, x[MAXN], y[MAXN], c[MAXN], d[MAXN], n, m, a[MAXN], siz, cnt[MAXN], pre[MAXN], suf[MAXN], c1[MAXB][MAXN], c2[MAXB][MAXN];
struct BT {int id, c;} b[MAXN]; lint ansR[MAXB][MAXN], ansL[MAXB][MAXN];
int cmp(BT p, BT q) {return p.c < q.c;}
struct BITS1 {
int t[MAXN];
void update(int x, int k) {for(; x <= n; t[x] += k, x += x&-x);}
int query(int x) {int res = 0; for(; x > 0; res += t[x], x -= x&-x); return res;}
} T1;
struct BITS2 {
int t[MAXN];
void update(int x, int k) {for(; x > 0; t[x] += k, x -= x&-x);}
int query(int x) {int res = 0; for(; x <= n; res += t[x], x += x&-x); return res;}
} T2;
int merg(int *p, int *q, int lp, int lq) {
int i = 1, j = 1, res = 0;
while(i <= lp && j <= lq)
if(p[i] < q[j]) ++i; else res += lp - i + 1, ++j;
return res;
}
int main() {
fastIO::init();
n = read(); m = read(); siz = 500;
for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = (BT) {i, a[i]};
for(int i = 1; i <= bl(n); ++i) {
sort(b+L(i), b+R(i)+1, cmp);
for(int j = L(i); j <= R(i); ++j) d[j] = b[j].id, c[j] = b[j].c;
for(int j = L(i); j <= R(i); ++j) pre[j] = T2.query(a[j]), T2.update(a[j], 1);
for(int j = L(i); j <= R(i); ++j) T2.update(a[j], -1);
for(int j = R(i); j >= L(i); --j) suf[j] = T1.query(a[j]), T1.update(a[j], 1);
for(int j = R(i); j >= L(i); --j) T1.update(a[j], -1); P[L(i)] = pre[L(i)];
for(int j = L(i)+1; j <= R(i); ++j) P[j] = P[j-1] + pre[j];
}
for(int k = 1, i = 1; i <= n; ++i) {
++cnt[a[i]];
if(i == R(k)) {
for(int j = 1; j <= n; ++j)
c1[k][j] = c1[k][j-1] + cnt[j];
for(int j = n; j >= 1; --j)
c2[k][j] = c2[k][j+1] + cnt[j];
++k;
}
}
for(int i = 1; i <= bl(n); ++i)
for(int j = L(i); j <= n; ++j)
ansR[i][j] = ansR[i][j-1] + (c2[bl(j)-1][a[j]+1] - c2[i-1][a[j]+1]) + pre[j];
for(int i = 1; i <= bl(n); ++i)
for(int j = R(i); j >= 1; --j)
ansL[i][j] = ansL[i][j+1] + (c1[i][a[j]-1] - c1[bl(j)][a[j]-1]) + suf[j];
lint ans = 0;
for(int l, r; m--; ) {
l = read(); r = read(); l ^= ans; r ^= ans;
if(l > r) swap(l, r); ans = 0; cx = cy = 0;
if(bl(l) == bl(r)) {
for(int i = L(bl(l)); i <= R(bl(l)); ++i)
if(l <= d[i] && d[i] <= r) y[++cy] = c[i];
else if(d[i] < l) x[++cx] = c[i];
ans = P[r] - ((l == L(bl(l))) ? 0 : (P[l-1])) - merg(x, y, cx, cy);
print(ans); print('\n');
} else {
ans = ansL[bl(r)-1][l] + ansR[bl(l)+1][r] - ansL[bl(r)-1][L(bl(l)+1)];
for(int i = L(bl(l)); i <= R(bl(l)); ++i) if(d[i] >= l) x[++cx] = c[i];
for(int i = L(bl(r)); i <= R(bl(r)); ++i) if(d[i] <= r) y[++cy] = c[i];
ans += merg(x, y, cx, cy);
print(ans); print('\n');
}
} fastIO::flush();
}
```