自动搬运

查看原文

来自洛谷，原作者为

	yllcm 模拟赛的你，再强大也是假的

搬运于2025-08-24 22:49:36，当前版本为作者最后更新于2023-10-05 09:27:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑容斥，枚举 $S$，那么条件相当于包含矩形 $(\min x_{S_i},\max x_{S_i}\min y_{S_i},\max y_{S_i})$，可以做到 $\mathcal{O}(2^k)$。

发现完全在矩形内部的点不影响限制，假设 $T$ 在矩形内部，那么钦定边界上的点选择的集合之后，它的贡献是 $\sum_{T_0\subseteq T}(-1)^{|T_0|}=[T=\varnothing]$，说明只有 $T$ 是空集的矩形有贡献，我们只需要考虑这些矩形。

假设所有点的横纵坐标互不相同，那么可以证明合法的矩形是 $\mathcal{O}(k^2)$ 的，因为假如我们枚举横坐标最小 / 最大的点，假设为 $p,q(y_p<y_q)$，那么矩形的纵坐标的下边界只有可能是 $y_p$ 或者在 $p,q$ 横坐标之间的点集中 $y_p$ 的前驱，上边界同理。所以任意两个点最多有 $4$ 个不同的矩形。

考虑横纵坐标有相同的情况，我们不妨给点钦定互不相同的标号，使得按照标号横坐标 / 纵坐标的权值不降，那么将这些互不相同的标号看做互不相同的横纵坐标，跑上面的算法，仍然是正确的。

所以问题转化为如何 $\mathcal{O}(1)$ 求包含某个矩形的所有正方形的大小之和。假设矩形为 $[x,y,z,w]$（描述横坐标区间为 $[x,y]$，纵坐标区间为 $[z,w]$），那么考虑边长为 $d$ 时，左下角位置点 $(u,v)$ 的条件（以下只讨论 $u$，$v$ 是对称的）

• $u\in[y-d+1,x-1]$。
• $u\in [0,n-d]$。

容易发现两个区间均非空时（$d\in [y-x+2,n]$）时刻有交，所以 $u$ 的取值个数是 $\min(x-1,n-d)-\max(y-d+1,0)+1$。所以列出式子：

$$\sum_{d}d^2(\min(x-1,n-d)-\max(y-d+1,0)+1)(\min(z-1,m-d)-\max(w-d+1,0)+1) $$

这是一个不超过 $4$ 次 / $5$ 段的分段函数，分段后直接求出前缀和即可。code