本文共 1175 字，大约阅读时间需要 3 分钟。

题目

题意概要

数据范围与约定

思路

使用类似于 尺取法 的方法。或者叫做双扫描线吧。平行于 $y$ 轴的扫描线。

对于左端点是 $l$ 、右端点是 $r$ 的情况，我们认为在这之间存在边长为 $r-l+1$ 的正方形。试图将 $r$ 增大一，我们求一个最宽的上下界 $u,d$ ，满足第 $u$ 行、第 $u+1$ 行、第 $u+2$ 行，一直到第 $d$ 行，都是没有建筑物的。

形如

如果这个空隙 $u-d+1$ 是大于等于 $r-l$ 的，那么就可以将 $r$ 增大 $1$ 。

这个空隙的大小，可以使用线段树解决。解决一个 “最长全零子段” 的问题。

维护线段树，可以通过 “遇到右端点就区间减、左端点就区间加” 的方法。

然后没了。如果你对时间复杂度 $\mathcal{O}(n\log n)$ 不太放心，有几个优化：

• 对纵坐标进行离散化，线段树的值域降为 $\mathcal{O}(p)$ 的。
• 对横坐标进行离散化（注意到合法的、最大的 $r$ 总是在某个建筑的左端点旁边），尺取次数降为 $\mathcal{O}(p)$ 。

两者同时使用，理论上来说，是 $\mathcal{O}(p\log p)$ 的。但是伪代码中没有使用；你也没必要做的这么绝。

代码

此处仅提供伪代码作为参考。因为我还没写出来

SegmentTree st;void work(){   	int l = 1, r = 0, ans = 0;	while(r != n and l <= n){   		while(r < n){   			for(左端点是第r+1列的矩形mat)				在线段树中将[up,down]增大1			if(st.query() >= r-l)				++ r; // query() 为最大全零子段			else 撤销本轮的add操作 		}		ans = max(ans,r-l+1);		for(右端点是第l列的矩形mat)			在线段树中将[up,down]减少1		++ l; // 强制移动一下l 	}	cout << ans << endl;}