菜王的 blog

场上没调出来，写个题解纪念一下。来一个值域无关的线性做法。

统计区间数量，一个经典的套路是考虑扫描线。

具体地，我们将右端点 $r$ 从左往右扫，并同时对于所有 $1 \le l \le r$ 的左端点 $l$，维护区间 $[l, r]$ 能生成的所有矩形。即，我们需要维护一个若干个三元组构成的集合 $S$，其中，$S$ 中的一个三元组 $(h, w, l)$ 代表区间 $[l, r]$ 能够生成矩形 $(h, w)$。

每次 $r \to r + 1$ 时，我们先更新 $S$ 内的所有三元组，丢掉不合法的，并加入 $[r, r]$ 所对应的集合 $(h_r, w_r, r)$，最后令 $ans \gets ans + cnt$。其中 $cnt$ 为集合内本质不同的左端点个数。

考虑形式化我们要支持的具体操作：

给你两个数 $H, W$，你要进行以下操作：

1. 新建一个集合 $S'$，并将 $(H, W, r)$ 加入 $S'$。
2. 对于 $S$ 内的每个三元组 $(h, w, l)$，你要执行以下操作：
   • 若 $h = H, w = W$，将 $(2h, w, l), (h, 2w, l)$ 加入 $S'$。
   • 若 $h = H, w \ne W$，将 $(h, w + W, l)$ 加入 $S'$。
   • 若 $h \ne H, w = W$，将 $(h + H, w, l)$ 加入 $S'$。
   • 若 $h \ne H, w \ne W$，则什么都不做。
3. 令 $S \gets S'$。

这个操作看起来很棘手，不好快速维护。所以我们考虑发掘一些性质；具体地，我们注意到，对于刚进行过 $H, W$ 操作得到的集合 $S$ 中的每一个三元组 $(h, w, l)$，一定有 $h = H$ 或 $w = W$。于是我们维护的东西一下就从二维的形式变成一维的形式了。

我们考虑换一下维护方式，转为维护两个若干个二元组构成的集合 $Sw, Sh$，并且记录 $lh, lw$ 分别为上次操作的 $h, w$。类似的，其中 $Sw$ 中的一个二元组 $(h, r)$ 代表区间 $[l, r]$ 能够生成矩形 $(h, lw)$，$Sh$ 中的一个二元组 $(w, r)$ 代表区间 $[l, r]$ 能够生成矩形 $(lh, w)$。那么我们可以直接维护了：

1. $H = lh, W = lw$。我们事先将 $(H, l), (W, l)$ 分别从 $Sw, Sh$ 里删除，这样就可以直接分别给 $Sh, Sw$ 两个集合打上整体加的 tag，最后再将 $(2H, l), (2W, l)$ 分别加入 $Sw, Sh$ 里即可。

2. $H = lh, W \ne lw$。类似地，事先将 $(W, l)$ 从 $Sh$ 里删除，给 $Sh$ 打上整体加的 tag；而对于 $Sw$，我们注意到 $Sw$ 在操作后至多会有 $O(1)$ 个元素，所以我们直接暴力清空 $Sw$，最后再将 $(2H, l), (2W, l)$ 分别加入 $Sw, Sh$ 里即可。$H \ne lh, W = lw$ 的情况是等价的。

3. $H \ne lh, W \ne lw$。这样，$Sh, Sw$ 在操作后都至多会有 $O(1)$ 个元素，所以类似地暴力清空即可。

注意到上述过程中每次只会插入 $O(1)$ 次，删除总共 $O(n)$ 次，均摊 $O(1)$ 次。并且当我们要删除元素时，要么只删除 $O(1)$ 个元素，要么只剩 $O(1)$ 个元素，所以被我们访问到但不被删去的元素个数每次是 $O(1)$ 的。

所以总插入删除访问次数是 $O(n)$ 的。直接使用两个哈希表维护，同时开一个桶记录左端点为 $l$ 的三元组的出现次数，即可做到 $O(n)$。如果手写哈希表记得不要用 memset 清空 head 数组，要对于已插入的元素手动清空。

code