X 最后更新于 2025-05-02 08:45:52

## 二维分块 ### [U210802 人类智慧分块](https://www.luogu.com.cn/problem/U210802)  我们将平面划分成 $n^{\frac 1 2}$ 个边长为 $n^{\frac 3 4}$ 的橙色大正方形，**所有的橙色大正方形视为一个部分**。 然后将每个橙色大正方形分成 $n^{\frac 1 2}$ 个边长为 $n^{\frac 1 2}$ 的蓝色小正方形，平面上共有 $n$ 则个蓝色小正方形。**所有位于同一个橙色大正方形的蓝色小正方形视为一个部分**。  将平面分为 $n^{\frac 3 4} $个 $n^{\frac 3 4} \times n^{\frac 1 2}$ 的黄色扁条矩形。从下到上依次划分成 $n^{\frac 1 4}$ 个 $n\times n^{\frac 3 4}$ 的部分，**每个部分有 $n^{\frac 1 2}$ 个黄色扁条矩形。（每一部分的黄块的并是一整行的橙块）**  将平面分为 $n^{\frac 3 4} $个 $n^{\frac 1 2} \times n^{\frac 3 4}$ 的绿色长条矩形。从左到右依次划分成 $n^{\frac 1 4}$ 个 $n^{\frac 3 4} \times n$ 的部分，**每个部分有 $n^{\frac 1 2}$ 个绿色长条矩形。（每一部分的绿块的并是一列橙块）** 发现每个点所在的橙色，蓝色，黄色，绿色矩形的所在部分都只有 $n^{\frac 1 2}$ 个同类矩形。我们对于**每个部分**都**独立维护**前缀和。 查询时可以划分成下图的样子：  容易发现除了紫色的零散部分其他每种颜色的贡献都可以 $O(1)$ 得到（单点修时 $O(\sqrt n)$ 进行后缀加）。 考虑紫色部分的贡献。这个时候可以运用题目给的性质：所有点的 $x,y$ 坐标都互不相同。这意味着点在紫色部分的分布是**非常稀疏**的，一定不超过 $O(\sqrt n)$ 级别。 因为要 $O(1)$ 查还是考虑用反演的方式去看一个点可以对哪些矩形产生贡献。  我们将 $x$ 轴与 $y$ 轴分块，块长 $\sqrt n$ 。这里以 $y$ 轴为例进行讲解。 我们对每个块开个 ```vector``` 存储顶点在这个块内的矩形的信息。对于一个点 $(x,y)$，其会对块内满足 $x\le u,y\le v$ 的矩形产生贡献。我们暴力枚举所有块内的矩形依次判断即可。我们从矩形顶点的角度分析复杂度，一个矩形顶点最多与 $\sqrt n$ 个点位于同一块内。所以总复杂度 $O(m\sqrt n)$($m$ 为矩形个数)。 ### 一些细节： - 最好令 $n\gets \lceil n^{\frac 1 4}\rceil ^{4}$，使得 $n^{\frac 1 2}$ 一定是 $n^{\frac 1 4}$ 的整数倍数。不然不同颜色的块之间可能出现交叉重叠。 - 散块的点中 $x$ 与 $u$ 在同一块且 $y$ 与 $v$ 在同一块中的这种点的贡献不能算重。 --- ### [P7448 [Ynoi2007] rdiq](https://www.luogu.com.cn/problem/P7448) & [区间本质不同逆序对](https://www.luogu.com.cn/problem/P7601) 考虑弱化版区间逆序对数 [P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) 的 $O(n\sqrt m)$ 的莫队做法。 这个题也上莫队，考虑转移。考虑当前莫队区间 $[l,r-1]$ 转移到 $[l,r]$ (其余情况同理)。记最大的满足 $a_x=a_r$ 的 $x$ 为 $pre_r$（若没有则为 $0$）。 则只有 $[\max(l,pre_r+1),r-1]$ 的部分的数能产生贡献。 所以最后能产生贡献的位置 $i$ 应满足 $pre_i<l~\land i\in [\max(l,pre_r+1),r-1] ~ \land a_i<a_r$。 考虑这是一个三维数点的形式，我们可以通过扫描线+莫队二次离线干掉 $pre_i<l$ 这一维（从右往左扫,只保留每个数最靠左出现的位置）。 然后剩下的两维可以简单差分一下表示成两个 $2-side$ 矩形。用之前说的二维分块维护即可。 为了让点稀疏，即使$x,y$ 互不相同，我们考虑将序列离散化成一个排列，满足相同的数离散化后的值靠左的比靠右的更小（容易发现这样不会影响答案）。