题解：CF685D Kay and Eternity

· · 题解

算法：扫描线。

题意

在平面上给定 n 个点，对每个 x \in [1, n] 分别计算包含了恰好 x 个点的 k \times k 的矩形的个数。

位置 (x, y) 表示从上往下数第 i 行，从左往右数第 j 列的交点。

转化

称原题中的矩形为第一类矩形，有一个很巧妙的转化是从统计矩形个数改为统计每个点的贡献。

令某个第一类矩形的右下角为 (x_1, y_1)，该矩形能包含点 (x_2, y_2) 等价于 x_2 \leq x_1 \leq x_2 + k 且 y_2 \leq y_1 \leq y_2 + k。则能使第一类矩形包含该点的合法矩形右下角同样构成一个矩形，称此类矩形为第二类矩形。

题意转化为对每个 x \in [1, n] 分别计算有多少个点恰好被 x 个 k \times k 的矩形包含。这里的点为第一类矩形的右下角，即所有整数坐标的点，有效点的数量级是 O(nk^2) 的，离散化之后有效点的数量级是 O(n) 的。

扫描线

考虑逐行扫描。取出第二类矩形，得到上下边界，当扫到边界时，在左右边界内暴力修改，然后统计答案就可以了。因为有效点不多，暴力修改复杂度是对的。

Code