Solution-P9563

· · 题解

考虑容斥，枚举 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 是对称的）

容易发现两个区间均非空时（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