题解：AT_abc420_f [ABC420F] kirinuki

· · 题解

大喵喵题。

一、题意

给定 n\times m 的 01 矩阵，求面积不超过 k 的全零子矩阵的数量，n\times m\le 5\times 10^6。

临近 CSP，本蒟蒻将一档一档时间复杂度讲解这道题目。

二、算法一

我会暴力！

直接枚举上下左右边界，前缀和判断，时间复杂度 \operatorname{O}(n^2m^2)，肯定 T 飞，本蒟蒻没写（想必大家都会吧）。

三、算法二

我会贡献计算！

我们可以枚举上下边界 u,d，然后将每一列 d-u+1 个数缩成一个数（把它们加起来），然后我们对于每个位置，维护其前方的最长连续全零子序列长度 len，然后这次贡献就是 \min(len,\lfloor \frac{k}{d-u+1}\rfloor) 了。时间复杂度 \operatorname{O}(n^2m)。最坏情况是 n 达到最大，仍然 T 飞。

四、算法三

我会根号分治！

发现如果 n\le \sqrt{nm}，则如上算法优秀，否则，我们直接旋转矩阵即可，时间复杂度 \operatorname{O}(nm\sqrt{nm})。如果良心出题人把 nm 的最大值设为 5\times 10^5 就过了，如今仍然 T 飞。算法三的提交记录。

五、算法四

我会并查集和线段树！

我们考虑仍然枚举上下边界，这一步是 \operatorname{O}(nm) 的。

然后我们考虑我们能否动态维护我们之前枚举一列的过程，首先我们都倒着枚举上下边界，然后对于每一列，可以算出这一列比上边界低的 1 中，最靠上的那个，假设它在第 h 行，则当我们的下边界枚举到 h-1 时，这个位置从不可用变为可用。

动态联通块就是经典的并查集问题啦，我们用并查集维护连通块大小，那么对于一个大小为 sz 的连通块，我们相当于产生了一个 sz\times sz 的三角阵，然后我们贡献对 mx 取最小值相当于我们截取前 mx 行，数其中点的数量。

我们可以使用线段树维护这个三角阵每一行的点数，然后区间求和。对于维护每一行，我们先把他视作方阵，然后我们再减去一个倒三角（第 i 行有 i 个点）即可。

虽然说我们成功的把时间复杂度降到了 \operatorname{O}(nm\log nm)，但线段树常数巨大无比，仍然会 T，但大部分都 AC 了。算法四的提交记录

六、算法五

我会树状数组！

由于线段树的巨大常数 和紧迫的时间限制，我们不得不请出树状数组上阵。

我们观察上面代码里的结构体 Seg，我们只需要将其用树状数组实现即可。

树状数组必要维护前缀和，当我们对前缀 [1,x] 全体加 y 时，1 的前缀和加了一个 y，2 加了两个，i 加了 i 个……到了 x+1 之后我们就只加 xy 了。

当我们对区间 [1,x] 中第 i 个数加 y\times i 时，我们 1 的前缀和加了一个 y，2 加了三个，i 加了 1+2+\dots+i=\frac{i(i+1)}{2} 个 y……到了 x+1 以后我们就只加 \frac{x(x+1)y}{2} 了。

我们把贡献拆成多少个 1，多少个 i 和多少个 \frac{i(i+1)}{2}，然后用差分维护每次区间加，然后单点查前缀和即可。

时间复杂度 \operatorname{O}(nm\log nm)，常数相对于算法四减少了很多（实测快三倍）

需要火车头、inline 等优化，然后我们可以特殊处理差分数组的第一个位置（它经常改动），并手动 \operatorname{O}(1) 维护它，这样能少大约 \frac{1}{3} 的常数。算法五的 AC 记录

七、后记

个人认为这道题目还是比较有趣的一道题，比这次套路 G 题有趣也困难很多。

本题解虽然比官方解法多一个 \log，但只用到了普及算法（并查集、树状数组）和较为明显的贡献计算、根号分治思想，而且实现难度不高。官解传送门