Home Archives Tags Friends About
悬线法及其与笛卡尔树的关联
2022-09-27

因为我学习了一年半的单调队列之后才知道世界上还有单调栈这种东西，三观碎裂，所以我对单调栈一直是比较排斥的。

有一段时间看见单调栈就抑郁，所以做题的时候就东贺贺，西贺贺，最终了解到了世界上还有一种很神奇的方法叫悬线法。

你可以从置顶文章中看出我一直很想写悬线法，结果当然是我咕咕咕了（

例题：土豪聪要请客

https://www.becoder.com.cn/contest/2870/problem/4

题意简述：给定一个 \(n\times m\) 的矩阵，其中有一部分地方有障碍。在整个地图上找到周长最大的、不包含障碍的矩形。

输入一个由 .（空地）和 X（障碍）组成的矩阵，输出最大矩形周长减 \(1\)。

一些鲜花

看到题过后第一时间想到悬线法，但是中午太困了处于游离状态一直掉线，所以干瞪着电脑屏幕打瞌睡。

于是这篇文章从 220927 被拖到了 230916，哈哈真神奇 现在是 231004 了，我才动笔。

首先预处理出 \(s_{i, j}\)，表示从 \((i,\,j)\) 向上，共有多少个连续的 .。

for (int i = 1; i <= n; ++i) {
	for (int j = 1; j <= m; ++j)
		s[i][j] = (a[i][j] == '.' ? s[i - 1][j] + 1 : 0);
}

悬线法的名字很形象，拎着一根细线的头，让它自然下垂。

为了方便思考和实现，我们这样想象：一个地图，我们手里拿着一根硬棒朝上举，然后固定我们手只能在一行上运动，用它左右「刷」沿途的矩形。

具象地说，选定一行 \(i\)，枚举每一个 \(j\)，寻找以第 \(i\) 行为底，包含 \((i,\,j)\)，高为 \(s_{i,\,j}\) 的最宽矩形。

也就是从 \((i, j)\) 出发，往左右分别找到最远的一个位置 \(L_j, R_j\)，满足 \(s_{i, L_j \sim R_j} \ge s_{i, j}\)。那么悬线法最抽象的部分就讲完了，接下来是最神奇的部分。

在第 \(i\) 行内，从每个 \((i, j)\) 开始找到 \(L_j, R_j\)，如果暴力那么明显是个 \(\mathcal O(m^2)\) 的时间。

但是我们考虑这么一件事情。假设 \(L_{i-1}\) 已经求出。

令 \(k = j-1\)，\(L_j\) 初值赋为 \(j\)（左端点至少是自己）。

  1. 当 \(L_j=1\) 时 即刻停止算法，因为 \(1\) 是可达的最左位置，不能再往左了。
  2. 当 \(a_k > a_j\) 时 \(a_k\) 就像一堵墙，堵住了我们要继续往左刷的硬棒，故不改变 \(L_j\) 并停止算法。
  3. 否则，由于 \(a_{L_k\sim k}\ge a_k\ge a_j\)，从 \(j\) 开始往左刷至少都能够到 \(L_k\)。此时我们令 \(k=L_k-1\)，回到第一步。

我们就可以求解到正确的 \(L_j\) 的。求解 \(R_j\) 的流程和上述大致相同，不再赘述。

那么是一个非常神奇的事情。悬线法的时间复杂度怎么证明呢？

我们思考。假设 \(a_{j-1}>a_j\)，算法会即刻停止；否则，当前定位直接跳到 \(L_{j-1}\) 之前，也就是说，为了求解 \(L_{j-1}\) 而遍历过的位置，求解 \(L_j\) 时都不会再遍历第二遍。

没有值会被遍历第二遍，所以是 \(\mathcal O(m)\) 的。

按照上述流程，算法总体时间复杂度 \(\mathcal O(n\times m)\)，和单调栈完全一致。

namespace XSC062 {
using namespace fastIO;
const int maxn = 2e3 + 5;
int n, m, ans;
char a[maxn][maxn];
int s[maxn][maxn], l[maxn][maxn], r[maxn][maxn];
inline int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	read(n);
	read(m);
	for (int i = 1; i <= n; ++i)
		scanf("%s", a[i] + 1);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)
			s[i][j] = (a[i][j] == '.' ? s[i - 1][j] + 1 : 0);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			l[i][j] = j;
			while (l[i][j] > 1 && s[i][j] <= s[i][l[i][j] - 1])
				l[i][j] = l[i][l[i][j] - 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = m; j; --j) {
			r[i][j] = j;
			while (r[i][j] < m && s[i][j] <= s[i][r[i][j] + 1])
				r[i][j] = r[i][r[i][j] + 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (!s[i][j])
				continue;
			ans = max(ans, (s[i][j] +
					  (r[i][j] - l[i][j] + 1)) * 2);
		}
	}
	printf("%d", ans - 1);
	return 0;
}
} // namespace XSC062

上述处理 \(s\) 数组的「竖向压缩」技巧是处理矩阵类悬线法题目的常用技巧，这里使用另一道题来举例子。

E. 玉蟾宫 / City Game / 城市游戏

https://www.becoder.com.cn/contest/1655/problem/2

这道题和上一道非常相似，只需改变求答案的式子即可。

namespace XSC062 {
using namespace fastIO;
const int maxn = 1e3 + 5; 
char t;
int n, m, ans;
int s[maxn][maxn];
int l[maxn][maxn], r[maxn][maxn];
int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%1s", &t);
			if (t == 'F')
				s[i][j] = s[i - 1][j] + 1;
			l[i][j] = j;
			while (l[i][j] > 1 && s[i][j]
						<= s[i][l[i][j] - 1])
				l[i][j] = l[i][l[i][j] - 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		r[i][m + 1] = m + 1;
		for (int j = m; j; --j) {
			r[i][j] = j;
			while (r[i][j] < m && s[i][j]
						 <= s[i][r[i][j] + 1])
				r[i][j] = r[i][r[i][j] + 1];
			ans = max(ans, s[i][j] *
						(r[i][j] - l[i][j] + 1));
		}
	}
	print(ans * 3, '\n');
	return 0;
}
} // namespace XSC062

值得注意的是，悬线法仅指求解最远左右端点的技巧。

同时可以维护过程中的其它信息，例如 情景剧 一题。链接中有详细叙述，此处略。

根据本题带来的启发，我们认识到悬线可在求解过程中维护的内容更多。

不像你单调栈随随便便删这删那信息全部断层什么都维护不了

upd on 240704

学习了笛卡尔树。现在介绍悬线与笛卡尔树的关系。

容易发现元素 \(i\) 的 \(l_i,r_i\) 二值就是其在笛卡尔树上对应的区间。

更抽象的一点是悬线法中跳一跳的操作在笛卡尔树中的对应内涵。以小根堆为背景、在 \(l\) 上向左跳为例，注意到该操作相当于从左到右向笛卡尔树中新增节点。

这也进一步验证了悬线法复杂度的正确性：我们都知道，在新加入节点时，若从树中提取出由根节点和其一直向右走直到节点不存在右儿子构成的链，则该点被添加到链中某一点的右儿子，该点原本的右子树（完整包含了链的剩余部分）成为新建节点的左子树。

而悬线实现的就是从链的最低点暴力爬山，直到找到合法点；而根据上面的结论，被枚举过的链上较低点不会作为新节点的右边的子孙，自然也不会再次被枚举到。

故而每个点最多被枚举到一次，得证。

进一步的，可以开发出悬线法 \(\mathcal O(n)\) 建笛卡尔树的方法：

每次求解完 \(l_i\) 后，令 \(rc_{l_i-1}=i\) 即可（当然 \(rc_{l_i-1}\) 是会被多次更新的，这也是不直接用邻接表 / 前向星连边的原因），\(r_i\) 与 \(lc\) 同理。

for (int i = 1; i <= n; ++i) {
	l[i] = i;
	while (l[i] != 1 && a[l[i] - 1] > a[i])
		l[i] = l[l[i] - 1];
	rc[l[i] - 1] = i;
}
for (int i = n; i; --i) {
	r[i] = i;
	while (r[i] != n && a[r[i] + 1] > a[i])
		r[i] = r[r[i] + 1];
	lc[r[i] + 1] = i;
}

其中，根节点即为 rc[0] 或 lc[n + 1]。

进一步从笛卡尔树出发，探究悬线法能够循环内维护的数据特点。

为何是循环内维护？因为循环外维护就只能从左右的直接儿子进行更新，那和笛卡尔树就没有区别了。

但其实结果是没什么可探究的，因为其经过的节点——自己左子树下最右端链——实在不具有什么特殊性，它们所对应的区间——从 \([l_i, i - 1]\) 到 \([i - 1, i - 1]\) 也看不出什么值得研究的，更何况可以被笛卡尔树更具象地代替。

所以我们认为这次悬线法的开发最终以失败告终，不然它早被别人开发了，我在此能给出的意见是，可以用悬线法完成矩形题目等不需要笛卡尔树树形结构的问题，至于其他，甚至包括上面提到的 情景剧 一题，都可以直接上笛卡尔树。

但笛卡尔树的建树我还是肯定会用悬线的！毕竟照应开头，我不会单调栈 😎

一言 - Hitokoto