题解：[ABC394G] Dense Buildings

通过观察，首先可以得出几个小结论：

$(a_i,b_i,y_i) \to (c_i,d_i,z_i)$ 的其中一条最优路径一定是 $(a_i,b_i,y_i) \to (a_i,b_i,w) \to (c_i,d_i,w) \to (c_i,d_i,z_i)$。
$w$ 越小，越有可能合法，满足单调性，因此可以二分答案，最后单组询问的答案即为 $y_i + z_i - 2 \times w$。
对于单组询问，可以从高到低进行相邻块合并，因此最后的答案检测可以转换为并查集检验两点的连通性。总共的时间复杂度为 $O(QV \alpha(HW) \log (V))$（其中 $V$ 便是高度的值域）。

考虑优化，不难发现各组询问直接相互独立，且可以离线操作，所以我们可以使用整体二分。首先将每组答案的 $l_i = 1,r_i = \min (y_i,z_i)$，对于一次二分操作，若此时 $l_i \le r_i$ 仍然成立，那么我们就尝试将 $\frac{l_i + r_i}{2}$ 作为该组询问的答案。检验的过程和单组询问大致相同，可以从高到低进行相邻块合并后检验连通性即可。时间复杂度就降到了 $O(Q\alpha(HW) \log (V))$，代码如下：

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
using namespace std;
const int M = 1e6;
const int MAXN = 505;
const int MAXQ = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,q,fl;
int fa[M + 5],sx[MAXQ],sy[MAXQ],sh[MAXQ],fx[MAXQ],fy[MAXQ],fh[MAXQ],l[MAXQ],r[MAXQ],ans[MAXQ],a[MAXN][MAXN];
vector <pair <int,int> > f[M + 5];
vector <int> res[M + 5];
int getfa (int u) {return fa[u] == u ? u : fa[u] = getfa (fa[u]);} 
void merge (int u,int v)
{
    u = getfa (u),v = getfa (v);
    if (u != v) fa[u] = v;
}
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    n = read ();m = read ();
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j) a[i][j] = read ();
    for (int i = 1;i <= n;++i)
    { 
        for (int j = 1;j <= m;++j)
        {
            if (i != n) f[min (a[i][j],a[i + 1][j])].push_back ({(i - 1) * m + j,i * m + j});
            if (j != m) f[min (a[i][j],a[i][j + 1])].push_back ({(i - 1) * m + j,(i - 1) * m + j + 1});//相邻块的预处理
        }
    }         
    q = read ();
    for (int i = 1;i <= q;++i)
    {
        sx[i] = read (),sy[i] = read (),sh[i] = read ();
        fx[i] = read (),fy[i] = read (),fh[i] = read ();
        l[i] = 1,r[i] = min (sh[i],fh[i]);//边界
    }
    while (!fl) //仍然有询问需要二分
    {
        fl = 1;
        for (int i = 1;i <= q;++i)
        {
            if (l[i] > r[i]) continue;
            int mid = (l[i] + r[i]) >> 1;
            res[mid].push_back (i);
            fl = 0;
        }
        for (int i = 1;i <= M;++i) fa[i] = i;
        for (int i = M;i >= 1;--i)
        {
            for (auto item : f[i]) merge (item.first,item.second);
            for (auto p : res[i]) // 第 p 个询问答案为 i 是否成立 
            {
                int u = (sx[p] - 1) * m + sy[p],v = (fx[p] - 1) * m + fy[p];
                u = getfa (u),v = getfa (v); 
                if (u == v) ans[p] = i,l[p] = i + 1;
                else r[p] = i - 1;
            }
        }
        for (int i = 1;i <= M;++i) res[i].clear ();
    }
    for (int i = 1;i <= q;++i) printf ("%d\n",sh[i] + fh[i] - 2 * ans[i]);
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}