题解 P4259 【[Code+#3]寻找车位】

Wen_kr · 2020-05-19 11:22:24 · 题解

观察到 m 和 q 都比较小，我们可以接受在复杂度里带上 m，比如 O(qm\log n)。

不妨考虑使用线段树来解决这个问题。

线段树上的一个节点描述的是 x 坐标在 [l,r] 区间内的最大正方形有多大。

因为第二种询问涉及两维，我们在一个节点上维护对于每一个 y，右边界落在 y 上的最大正方形有多大，这样我们每个节点都维护了 m 个量，空间复杂度是 O(4nm)，可以接受。

考虑怎么合并两个子区间。

容易发现的是，我们只需要考虑跨过 x=mid 这条线的正方形。

考虑这样一个矩阵：

--------------- x = r
0 0 0 0 0 1 1 0
1 0 1 1 0 1 1 0
1 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1
--------------- x = mid
1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 0 1 1
1 0 0 0 1 0 0 1
--------------- x = l

注意到我们只需要从 x=mid 这条线向上向下走连续的 1 长度，其他的 1 都是没用的，先将这些没用的 1 删去。

--------------- x = r
0 0 0 0 0 0 1 0
1 0 0 1 0 0 1 0
1 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1
--------------- x = mid
1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 1
0 1 1 1 0 0 0 1
0 0 0 0 0 0 0 1
--------------- x = l

然后将矩阵变形为长度：

--------------- x = r
3 1 1 3 1 1 4 1
--------------- x = mid
2 3 3 3 1 2 1 4
--------------- x = l

记上半部分的长度数组为 len1，下半部分的长度数组为 len2。

考虑对于一个 y=p 怎么求得答案：

最粗暴的方法是，我们二分一个左端点 q，那么 [q,p] 之间存在合法正方形的条件就是 \min_{q\leq i\leq p}\{len1_i\}+\min_{q\leq i\leq p}\{len2_i\}\geq p-q+1。

二分的时间复杂度是不优秀的，但是观察到随着 y 的递增左端点也一定递增，我们就能将这个二分删掉了。

我们只需要知道左端点到当前点之间两个长度数组的最小值，这可以使用单调队列解决。

这样我们就实现了对答案的计算，最后我们只需要计算出 len1 和 len2 数组。

在线段树上维护 up 和 down 表示每个节点对应子区间内从上往下最长的连续 1 长度和从下往上最长的连续 1 长度，这样在合并的时候左儿子的 down 就是我们上半的 len1，右儿子的 up 就是我们下半的 len2。