各質問への答えの求め方

まず、\(i\) \((1\leq i\leq Q)\) を \(1\) つ固定し、\(i\) 番目の質問の答えの求め方について考えます。

区画 \((A_i,B_i)\) の \(Y_i\) 階から区画 \((C_i,D_i)\) の \(Z_i\) 階への移動方法を \(1\) つ取り、その移動において通った最も低い階（どのビルかは問わない）を \(X\) とします。このとき、\(X\leq Y_i\), \(X\leq Z_i\) が成り立つことに注意します。また、通路の使用によって階数は変化しないことから、少なくとも階段を使って\(1\) つ下の階への移動を \((Y_i-X)\) 回以上、\(1\) つ上の階への移動を \((Z_i-X)\) 回以上行う必要があります。よって、階段の使用回数は \((Y_i+Z_i-2X)\) 回以上となります。逆に、階段の使用回数を \((Y_i+Z_i-2X)\) とするような移動は次のようにして可能です。

• 区画 \((A_i,B_i)\) のビル内で \(Y_i\) 階から \(X\) 階まで下がる。
• 元の経路と同じ順番で通路を使用し、ビルの間を移動する。ただし、それぞれのビルの \(X\) 階の間を結ぶ通路を使用する。
• 区画 \((C_i,D_i)\) のビル内で \(X\) 階から \(Z_i\) 階まで上がる。

このような移動は常に可能です。元の経路における移動は常に \(X\) 階以上の階の間で行われていること、\(X_1<X_2\) のとき、ある \(2\) つのビルの間で \(X_2\) 階同士の間を移動できるならば \(X_1\) 階同士の間は必ず移動できることに注意してください。
階段の使用回数を最小とするような移動方法についてそのようなものを考えることができるため、次のような移動方法の中に、階段の使用回数を最小とするものが存在します。ただし、\(1\leq X'\leq \min(Y_i,Z_i)\) です。ここで、\(\min(Y_i,Z_i)\) で、\(Y_i, Z_i\) のうち大きくない方の値を表します。

• 区画 \((A_i,B_i)\) のビル内で \(Y_i\) 階から \(X'\) 階まで下がる。
• （隣接する）\(X'\) 階建て以上のビルの間の通路のみを使って、区画 \((A_i,B_i)\) のビルから 区画 \((C_i,D_i)\) のビルまで移動する。
• 区画 \((C_i,D_i)\) のビル内で \(X'\) 階から \(Z_i\) 階まで上がる。

この移動における階段の使用回数は \(Y_i+Z_i-2X'\) であるため、このような移動方法のうち階段の使用回数を最小となるものは \(X'\) が最大であるものとなります。すなわち、問題の答えは次の条件をともにみたす最大の正整数 \(M_i\) を用いて \((Y_i+Z_i-2\min(M_i,\min(Y_i,Z_i)))\) と書けます。

• \(M_i\) 階建て以上のビルの間の通路のみを使って、区画 \((A_i,B_i)\) のビルから 区画 \((C_i,D_i)\) のビルまで移動することが可能である。

\(M_i\) は Union-find treeを用いて求めることができます。あらかじめ隣接する区画のビルのペアを、低い方のビルの高さを基準として降順にソートしておきます。ソートされた列の順にビルのペアの間を結んでいき、区画 \((A_i,B_i)\) のビルと区画 \((C_i,D_i)\) のビルが同一連結成分に初めて属した時の（ペアのうち低い方のビルの）高さが \(H_i\) となります。

問題の解法

これを \(i=1,2\ldots, Q\) に対して行えば良いです。方法はいくつかありますが、ここでは並列二分探索を用いた解法を紹介します。

これは、各\(i=1,2\ldots, Q\) について、最初、\(L_i=1\), \(R_i=\max(F_{i,j})+1\) に設定します。ここで、\(\max(F_{i,j})\) はビルの高さの最大値を表します。その後、次の操作を全ての \(i\) が \(R_i-L_i=1\) をみたすまで繰り返します。 なお、以下でも、先で述べたソートされたビルのペアの列を用います。

• Union-find 木を初期化する。
• 各 \(i=1,2,\ldots,Q\) について、 \(m_i=\left\lfloor \frac{L_i+R_i}{2}\right\rfloor\) を計算する。
• ビルのペアの列に従って、Union-find 木をmerge していく。その過程で、（ペアのうち低い方のビルの）高さ \(h\) 以上のビルの間がすべて結ばれた時点で、\(m_i=h\) であるような \(i\) すべてについて、区画 \((A_i,B_i)\) のビルと区画 \((C_i,D_i)\) のビルが同一連結成分に属しているかの判定を行う。属していれば新たに \(L_i=m_i\)、そうでなければ \(R_i=m_i\) とする。

最終的な \(L_i\) の値が \(M_i\) となります。 このとき、計算量は \(O(HW\log(HW)+(Q+HW)\alpha(HW)\log(\max(F_{i,j})))\) となります。ここで、\(\alpha(n)\) はアッカーマン関数の逆関数を表します。
これはこの制約下で十分高速であり、よってこの問題を解くことができました。

他にもマージテクを用いた解法なども存在します。

c++ による実装例:
（注：コードの単純化のため、計算量が \(O(\max(F_{i,j})\log(\max(F_{i,j})))\) だけ増加していますが、本問題の制約下では問題ありません。）

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

#define H 500
#define W 500
#define Q (int)2e+5
#define F (int)1e+6


int main(void){
	int h,w,q;
	int f[H][W];
	int a[Q],b[Q],y[Q],c[Q],d[Q],z[Q],l[Q],r[Q];
	vector<pair<int,int> >e[F+1];
	vector<int>check[F+1];

	cin>>h>>w;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>f[i][j];
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>a[i]>>b[i]>>y[i]>>c[i]>>d[i]>>z[i];
		a[i]--,b[i]--,c[i]--,d[i]--;
	}

	for(int i=0;i<h-1;i++)for(int j=0;j<w;j++)e[min(f[i][j],f[i+1][j])].push_back({i*w+j,(i+1)*w+j});
	for(int i=0;i<h;i++)for(int j=0;j<w-1;j++)e[min(f[i][j],f[i][j+1])].push_back({i*w+j,i*w+(j+1)});
	for(int i=0;i<q;i++)l[i]=1,r[i]=F+1;

	while(true){
		bool flag=true;
		for(int i=0;i<=F;i++)check[i].clear();
		for(int i=0;i<q;i++){
			if(r[i]-l[i]>1){
				check[(l[i]+r[i])/2].push_back(i);
				flag=false;
			}
		}
		if(flag)break;

		dsu uf(h*w);
		for(int i=F;i>=0;i--){
			int sz=e[i].size();
			for(int j=0;j<sz;j++)uf.merge(e[i][j].first,e[i][j].second);
			sz=check[i].size();
			for(int j=0;j<sz;j++){
				int idx_s=a[check[i][j]]*w+b[check[i][j]];
				int idx_t=c[check[i][j]]*w+d[check[i][j]];
				if(uf.same(idx_s,idx_t))l[check[i][j]]=i;
				else r[check[i][j]]=i;
			}
		}
	}

	for(int i=0;i<q;i++)cout<<(y[i]+z[i]-2*min(l[i],min(y[i],z[i])))<<endl;
	return 0;
}