题解：P8419 [THUPC 2022 决赛] riapq

_ATRI · 2026-01-31 12:13:09 · 题解

前言

发现我不会写分块分块分块，严肃学习了分块分块分块。
严肃参考 IOI 金牌大神的题解。

思路

题意很明确了。
不弱于区间逆序对，于是我们分块分块分块！！！

块长取根号是最优复杂度，那我直接用根号来讲吧。
设块长为 \sqrt{n} 对序列分块。接下来考虑每一次修改造成的几种贡献：

1. 左右散块内部
2. 左散块对右散块
3. 整块对左散块
4. 单个整块内部
5. 整块对整块
6. 左散块对整块

左右散块内部：

好做。预处理对于第 i 块中的第 j 个数，这一块的前 k 个数有多少比它小，复杂度 O(n\sqrt{n})。每一次修改直接在 b 数组上面加。

左散块对右散块：

好做。预先块内排序。每一次修改用指针扫一遍，直接在 b 数组上面加。给个代码。

//c[i].x 是值，c[i].y 是原序列位置 
int LL=belong[l],RR=belong[r];
int p=L[LL],sum=0;
for(int i=L[RR];i<=R[RR];i++){
    while(p<=R[LL]&&c[p].x<c[i].x)sum+=(c[p].y>=l),p++;
    if(c[i].y<=r)b[c[i].y]+=sum;
}

整块对右散块：

好做。预处理出前 i 块中有多少个数小于 j。直接拿个 O(\sqrt{n}) 单点修 O(1) 查的值域分块平衡一下复杂度。复杂度 O(n\sqrt{n})。每一次修改直接在 b 上加。

单个整块内部：

好做。修改时直接对每块打标记。询问时，用标记乘上块内询问点前面的数的贡献即可。可以直接用上做左右散块内部中预处理的数组。

整块对整块：

好做。维护对于每一个整块，其他块对它的贡献次数。用差分平衡一下复杂度，修改时枚举每一块 O(1) 修改这一块的差分数组，在查询时可以 O(\sqrt{n}) 复原出原数组然后统计。

左散块对整块：

不好做！

构建一个平面，x 坐标为块编号，y 坐标为 a 值。直接维护修改不好做，于是维护的是差分数组。
比如说对于 a 这个数，我们要在 l 到 r 的块上更新贡献，那么只需要修改 x 坐标为 l 和 r+1 上的点，在 y 坐标上加点就可以了。每一次询问就做一遍二维数点。

然后我们怎么维护它呢？我们对它进行分块分块分块。