P7601 [THUPC2021] 区间本质不同逆序对

区间本质不同逆序对。

/(/mathcal O(n /sqrt n /times /sqrt n)/) 应该谁都会做，而且谁都知道不能过。

回顾 P5047，考虑莫队二次离线。

记 /(f(l,r)/) 为 /([l,r]/) 中 /(>a_r/) 的数的种类数。

则区间转移从 /([l,r-1]/) 变成 /([l,r]/)，令 /(r’/) 为 /(a_r/) 上一次出现的位置，则贡献为 /(f(l,r)-f(l,r’)/)，其他方向和一连段转移同理。

考虑到种类数难以维护，尝试通过扫描线转换为总数，问题转化为 /(/mathcal O(n)/) 次单点修改，/(/mathcal O(n /sqrt n)/) 次矩阵和查询，第一维是下标，第二维是值域，此时点的横坐标和纵坐标一一对应，即横坐标和纵坐标两两不同。

我们需要一个针对上述问题的 /(/mathcal O(/sqrt n)-/mathcal O(1)/) 数据结构。

引入二维分块，即对 /(n/times n/) 的矩阵进行适当地分块，使得块数 /(/mathcal O(/sqrt n)/) 且支持 /(/mathcal O(/sqrt n)-/mathcal O(1)/) 或 /(/mathcal O(1)-/mathcal O(/sqrt n)/)。

首先用将整个矩形用 /(n^{0.75}/times n^{0.75}/) 来分块（如图红色部分），这样总块数为 /(/mathcal O(n^{0.25}/times n^{0.25}=/sqrt n)/) 的，整块复杂度保证。

考虑分剩余块，使得较小块复杂度保证，不证：

• /(n^{0.25}/times n^{0.25}/) 个 /(n^{0.75}/times n^{0.5}/) 大小的块，蓝色部分。
• /(n^{0.25}/times n^{0.25}/) 个 /(n^{0.5}/times n^{0.76}/) 大小的块，绿色部分。
• /(n^{0.25}/times n^{0.25}/) 个 /(n^{0.5}/times n^{0.5}/) 大小的块，橙色部分。

如图，例：/(155/)。

最后考虑灰色块复杂度，由于询问横坐标和纵坐标两两不同，而灰色块宽度不超过 /(/mathcal O(/sqrt n)/)，涉及的询问只有 /(/mathcal O(/sqrt n)/) 种，故散块修改 /(/mathcal O(/sqrt n)/)，查询 /(/mathcal O(1)/)，复杂度保证。

时间复杂度为 /(/mathcal O(n/sqrt n)/)，空间复杂度为 /(/mathcal O(n)/)。

CODE