P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I 笔记

对序列分块后，可以把查询的贡献拆分成以下四部分：

1. 中间整块间的逆序对数。
2. 左、右散块内部的逆序对数。
3. 左、右散块和中间整块间的逆序对数。
4. 左、右散块间的逆序对数。

对于第二部分，$O((\sqrt{n}{)}^2)$ 预处理一下每个块内前后缀的逆序对数即可。

对于第三部分，枚举散块的每个数，这样只需知道每个数在某个整块内的排名就好了，设 $c_{i,j}$ 表示块 $i$ 内数字 $j$ 的排名，再用前缀和 $s_{i,j}=\sum _{k=1}^i{c}_{k,j}$ 就能 $O(1)$ 查询一个数在一段区间的块内的排名之和。

对于第四部分，由于题目不涉及修改，并且有序序列的逆序对数可以用双指针 $O(\sqrt{n})$，因此提前对每个块进行排序，询问的时候把在区间内的数取出来双指针即可。

最后处理第一部分，设块 $[i,j]$ 的逆序对数是 $f_{i,j}$，则有 DP

$$f_{i,j}\leftarrow f_{i,j-1}+{\mathrm{pre}}_{j,\sqrt{n}}+\sum _{a_k\in \mathrm{Block}(j)}(s_{j-1,a_k}-s_{i-1,a_k})$$

状态数 $O(n)$，转移 $O(\sqrt{n})$，时间复杂度 $O(n\sqrt{n})$。