题目简述：给定一个$n imes m$的二维矩阵$a[i][j]$，其中$1 leq nm leq 2 imes 10^5$，矩阵元素$1 leq a[i][j] leq nm$且互不相等。一个区间$[l, r]$是【好】的，如果所有在$[l, r]$范围内的元素（在平面上）构成了一棵树。求【好】区间$[l, r](1 leq l leq r leq nm)$的个数。
解：code
建模：
令$G = (V, E)$表示二维矩阵$a[i][j]$对应的无向图，构造如下：
1. $ V = { 1, 2, dots, nm }, $
2. $ E = { (a[x_1][y_1], a[x_2][y_2]): (x1,y1)-(x2,y2) in { (0, 1), (0, -1), (-1, 0), (1, 0) } }. $
注意到这个图的特殊性，即每个点的度数都$leq 4$。
令$G_{l, r} = (V_{l, r}, E_{l, r})$表示$G$中包含节点$[l, r]$的子图，形式上，
1. $V_{l, r} = V cap [l, r], $
2. $E_{l, r} = E cap [l, r]^2. $
一个区间$[l, r]$是【好】的，如果$G_{l, r}$是一棵树。
对每个$1 leq r leq nm$，令$l_r$表示最小的$l$，使得$G_{l, r}$是无环图。则显然有$l_r leq l_{r+1}$。
对每个$r$，我们需要求出$l_r$，可以用 Link-Cut Tree 在$O(nm log nm)$的复杂度内做到。
令$c_{l, r}$表示$G_{l, r}$的 连通块/连通分支 （Connected Component） 的个数。
观察：$G_{l, r}$是一棵树，当且仅当$l_r leq l leq r$且$c_{l, r} = 1$。
因此，对每个$r$，只需统计$l in [l_r, r]$中满足$c_{l, r} = 1$的个数。
现在我们考虑$c_{cdot, r-1}$与$c_{cdot, r}$的关系。
假设已知$l in [l_r, r-1]$的$c_{l, r-1}$，设$(x, r) in E_{l_r, r}$，则$l_r leq x leq r$，增加$(x, r)$这条边后，会将$x$与$r$所在的连通块合并，从而使$l in [l_r, x]$时$G_{l, r}$比$G_{l, r-1}$的连通块个数，于是
$$ c_{l, r} = c_{l, r-1}+1 - sum_{(x, r) in E_{l_r, r}} [x geq l]. $$
这个可以用线段树来维护：从$c_{l, r-1}$到$c_{l, r}$的过程，需要
1. 区间$[l_r, r]$整体$+1$。
2. 对$(x, r) in E_{l_r, r}$，区间$[l_r, x]$整体$-1$。
其中，线段树节点维护的信息有：区间最小值，以及区间最小值出现的次数。
时间复杂度为$O(nm log nm)$。