ABC420F 题解

__vector__ · 2025-08-27 11:09:49 · 题解

好像就我用了这个奇怪的 O(nm\alpha(n) + m \log m) 做法，场上把两处 n,m 写反没调出来。

前置知识

并查集，树状数组，单调队列。

Solution

考虑枚举矩形的最左侧的那一列，统计对应的合法矩形个数，最后相加即可。

令 l_{i,j} 表示从格子 (i,j) 开始，向右延申最多多少格子，不会碰到障碍，格子 (i,j) 也计入统计。

那么，假设枚举到的是 (x,c),(x+1,c),\cdots,(y,c)，那么，假如不考虑矩形面积小于等于 k 的限制，那么对应的合法矩形个数将是 \min\limits_{i=x}^y l_{i,c}。

也就是说，在不考虑面积限制的情况下，一种枚举方案对应的矩形合法方案数仅取决于其 l 值最小的格子。

那么，考虑枚举这个 l 值最小的格子，计算出有多少种合法的枚举左侧第一列的方案，使得这个格子是 l 值最小的，那么假设不考虑面积限制，就可以直接得出答案了。

此处实现有一些简单的技巧：若同一列多个格子的 l 值一致，那么行数更小的格子视作 l 值更小；可以使用单调队列均摊 O(1) 求出每个格子的同一列最近的 l 值更小的格子。

现在考虑面积小于等于 k 的限制。

假设枚举了 (x,y) 作为 l 值最小的格子，令其 l 值为 p，且 (l-1,y),(r+1,y) 分别是 y 列中，与 (x,y) 最近的行数更小且 l 值更小的格子，与 (x,y) 最近的行数更大且 l 值更小的格子。

那么，原本没有面积限制的情况下，任意选择 l \le a \le b \le r，选中 y 列的 a 到 b 行的格子都是一种合理的枚举方案。

但是若 \lfloor \frac{b-a+1}{k}\rfloor \lt p，那么实际上枚举 (a,y),(a+1,y),\cdots,(b,y) 对应的合法矩形方案数仅会受到 b-a+1 的值的约束，而不是当前 (x,y) 的 l 值 p 的约束。

考虑先只统计 \lfloor \frac{b-a+1}{k}\rfloor \ge p，也就是 b-a+1 \le \lfloor\frac{p}{k}\rfloor 的情况。

::::info[现在需要求解一个这样的问题] 有 a+b-1 个从左到右排列的格子，一个非负整数 lim。

称从左边开始第 a 个格子为中心格子。

那么现在需要选择不超过 lim 个连续格子使得包含中心格子，问有多少种方案。
::::
:::::info[解决方案] 令 x 表示从中心格子开始向左边数，一共有多少个格子被选中了。。

现在，需要对于 \forall x \in [1,a]，计算出对应的合法的右端点的个数。

可能存在一部分 x，其右端点的可选集合必然是 [a,a+b-1]，要满足这个，则 x+b-1 \le lim，即 x \le lim-b+1。

那么这一部分 x 的总贡献就是 \max(0,lim-b+1)\cdot b。

对于 x \gt lim-b+1，其贡献将会是 \max(0,lim-x+1)。

这一部分的最小 x 将会是 \max(0,lim-b+1)+1，最大的 x 将会是 \min(lim,a)，分别求出贡献值，然后这一部分 x 的贡献的累加形式是一个等差数列，刚才求解了最大值最小值，并且公差为 1，直接算总和就行了。

时间复杂度 O(1)。
:::::

最后，需要统计有多少种选择方案 (a,y),(a+1,y),\cdots,(b,y) 满足 \lfloor\frac{k}{b-a+1}\rfloor \lt \min\limits_{i=a}^b l_{i,y}，每种此类方案都会再贡献 \lfloor\frac{k}{b-a+1}\rfloor 的答案。

考虑从小到大枚举 b-a+1 的值，计算有多少选择同一列连续 b-a+1 行的方案，使得不覆盖任意一个 l 值小于等于 b-a+1 的点。

随着 b-a+1 的增大，原来能覆盖的点不会变得不能覆盖，所以可以每次暴力更新能覆盖的点。

然后，对于一列中长度为 len 的极大的连续可覆盖格子，其贡献的选择方案数是 len-\lfloor\frac{k}{b-a+1}\rfloor+1。

那么，考虑定义两个数组 sum,cnt，每个 len 都会导致 sum_{len} \leftarrow sum_{len}+len,cnt_{len}\leftarrow cnt_{len}+1。

那么，当前 b-a+1 对应的选择方案数就是：