P7601 [THUPC2017] 区间本质不同逆序对
xfrvq
·
·
题解
\tt Link
题意
多次求区间逆序对，但是如果多个逆序对满足分别位置的值相等，那我们就只算一次。
## 选择方法&拆贡献
首先发现这个问题严格难于 [区间逆序对](/problem/P5047) 问题。区间逆序对的常见做法是 **分块** 或者 **二次离线莫队**，这里选择更好写且常数小的 **二次离线莫队**。
标识：记 $P_i,N_i$ 分别为与 $i$ 位置颜色相同的上一个/下一个位置。
假如我们莫队，那么从 $[l,r-1]$ 变成 $[l,r]$，答案会增加 $[P_r,r]$ 新出现的 $\gt a_r$ 的数的种类数。拆一下，就是 $[l,r]$ 中 $\gt a_r$ 的数的种类数，减去 $[l,P_r]$ 中 $\gt a_r$ 的数的种类数。
## 离线后转化问题
即使经过转化，我们要求的东西还是和 **种类数** 有关而非**总数**。所以我们对数组做一次扫描线，在扫到 $i$ 时，计算有关 $i$ 的贡献，同时**把 $P_i$ 的贡献消除**就行了。
于是现在的问题就是 **总数**，要求 **单点加，区间大于 $x$ 的数的个数**，考虑将其转化为二维形式，第一维是下标，第二维是值域，那么原问题就是一个 **带权二维数点**。
鉴于莫队二次离线的原理，我们把问题转换为：
+ 扫描线过程中，拆出 $O(n)$ 个修改（包括插入 $i$ 以及删去 $P_i$）
+ 给每个询问计算贡献，总共会有 $O(n\sqrt m)$ 次二维的查询。
于是你要合理的平衡复杂度，做到 $O(\sqrt n)$ 修改 $O(1)$ 查询。
别漏了几个性质。
+ 所有有值的点，$x$ 坐标互不相同，$y$ 坐标可能相同（因为是值域）。
+ 我们有一种方法让 $y$ 坐标也互不相同，即对于相同的 $y$ 坐标值，让 $x$ 坐标越小的 $y$ 坐标越小。
## 二维分块
~~刚看到这个概念以及这个问题的时候，我甚至已经准备好直接用 $\sout{n^{\frac 23}}$ 做块长暴力了~~
**注意：下面介绍的是一种 $O(\sqrt n)$ 前缀矩形加 $O(1)$ 单点查询的数据结构，原问题是 $O(\sqrt n)$ 单点加 $O(1)$ 前缀矩形和，二者本质一样。**
举个例子，假设我们要加的是这么一个矩形（左下角是原点，右上角是询问点）。
为了方便，以下记 $\mathbf a=n^{0.25},\mathbf b=n^{0.5},\mathbf c=n^{0.75}$。
首先因为整块复杂度要保证，所以块数是 $O(\sqrt n)$ 的，于是你就应该用 $\bf c\times c$ 来分块，这样总块数就是 $O(\mathbf{a\times a}=\sqrt n)$ 的。
但是我们整块复杂度保证，散块又不行了。于是考虑在现在的灰色部分分块用来辅助原来的散块，分出
+ $\bf a\times b$ 个 $\bf c\times b$ 的块
+ $\bf b\times a$ 个 $\bf b\times c$ 的块
+ $\bf b\times b$ 个 $\bf b\times b$ 的块
现在总共分了 $4$ 种块，对于每种块我们都维护块和。
现在来算一下复杂度。
+ 对于红色块而言，它一定不超过 $\sqrt n$ 个。
+ 对于橙色块而言，它一行最多只有 $n\div\mathbf c=n^{0.25}$ 个，一列最多只有 $\mathbf{c\div b}=n^{0.25}$ 个，乘起来不超过 $\sqrt n$ 个。
+ 对于蓝色块而言，它一行最多只有 $\mathbf{c\div b}=n^{0.25}$ 个，一列最多只有 $n\div\mathbf c=n^{0.25}$ 个，乘起来不超过 $\sqrt n$ 个。
+ 对于绿色块而言，它一行/一列最多只有 $\mathbf{c\div b}=n^{0.25}$ 个，乘起来也不超过 $\sqrt n$ 个。
+ 散块需要结合这题的特殊性质才可做，这里不作讨论，下面讲。
那散块如何做呢？
首先，散块本身的定义是：**一个询问覆盖了一个点但没有完全覆盖这个点所在的 $\bf b\times b$ 块**，就是上图中的黄色部分。
上文提到的性质，可以理解为：保证所有的 $x$ 坐标或 $y$ 坐标互不相同。
**基于性质**，我们把散块拆分为三部分。
对于紫色部分，枚举紫色范围内 $x$ 坐标，然后查看 $y$ 坐标是否也在紫色范围内，如果是就加上贡献。
对于粉色部分，枚举粉色范围内 $y$ 坐标，然后查看 $x$ 坐标是否也在粉色范围内，如果是就加上贡献。
你可以在紫色部分的时候算上蓝色部分，也可以在粉色部分的时候算上蓝色部分，不要算重就行了。
## 代码
[$\tt Code$](https://www.luogu.com.cn/paste/j50a2b67)
用宏定义，多个相同功能函数使用一个代替等的简化，我写的还算简洁，不到 2.5k，不到 100 行。
~~事实是因为使用大量宏定义简化导致一个字母打错调了一天~~