この問題では、\(N\) 個の点に関するクエリ（質問）が \(Q\) 個与えられています。制約を見ると、 \(Q\) は最大で \(N\) と等しくなるので、結局 \(N\) 個すべての点に対して実行時間制限以内に答えを求めるアルゴリズムが必要になります。

\(N\) 個の点のうち、点 \(P\) との距離が最も大きい点までの距離を求めるアルゴリズムを考えてみましょう。

まず初めに、 点 \(P\) に対して \(N\) 個の点候補との距離を全て調べてみて、最大値を求めるという方法が考えられます。これは \(1\) つの点について計算量が \(\Theta (N)\) かかってしまい、\(N\) 個の点についてこれを行うと全体で計算量が \(\Theta (N^2)\) となります。この問題の制約下では、この解法はまず実行時間制限に間に合いません。 これではダメなので、他の方法を検討しましょう。

問題文の折り畳み内にも書かれている通り、二次元平面上の2点 \(P_1 = (x_1, y_1)\) と \(P_2 = (x_2, y_2)\) とのマンハッタン距離は以下の通り定義されます。

• \(\mathrm{dist}(P_1, P_2) = |x_1 - x_2| + |y_1 - y_2|\)

注目すべきは、絶対値です。絶対値は、以下のように定義されます。

\( |X| = \left\{ \begin{array}{ll} X & (X \geq 0) \\ -X & (X \lt 0) \end{array} \right. \)

実は、絶対値は以下のようにも求められます。

\(|X| = \max(X, -X)\)

いろいろな \(X\) に対して \(|X|\) の値を2つの方法で実際に計算してみて、 \(2\) つの値が一致することを確かめてみて下さい。

さて、2つめの絶対値の求め方を使って、 \(\mathrm{dist}\) の式を書き替えます。

\( \mathrm{dist}(P_1, P_2) = \max(x_1 - x_2, x_2 - x_1) + \max(y_1 - y_2, y_2 - y_1) \)

\(x, y\) それぞれの \(\max\) の中の、左側と右側どちらが大きいかで合計4通りの場合分けがあります。これをすべて書き出すと、次のようになります。

\( \mathrm{dist}(P_1, P_2) = \max(x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1, x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1) \)

これをうまくくくってみると、以下のように式変形できます。

\( \max(x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1, x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1) = \max((x_1 + y_1) - (x_2 + y_2), (x_1 - y_1) - (x_2 - y_2), (x_2 - y_2) - (x_1 - y_1), (x_2 + y_2) - (x_1 - y_1)) \)

かなり複雑な式に見えますが、実はうまく置き替えるとシンプルになります。

\(X_1 = (x_1 + y_1), Y_1 = (x_1 - y_1), X_2 = (x_2 + y_2), Y_2 = (x_2 - y_2)\)

としたとき、

\( \max((x_1 + y_1) - (x_2 + y_2), (x_1 - y_1) - (x_2 - y_2), (x_2 - y_2) - (x_1 - y_1), (x_2 + y_2) - (x_1 - y_1)) = \max(X_1 - X_2, X_2 - X_1, Y_1- Y_2, Y_2 - Y_1)\)

となります。最初とあまり変わっていないように見えるかもしれませんが、式が \(X\) のみに依存する部分と、 \(Y\) のみに依存する部分にはっきり分かれていて、すべての最大値を取ればよいという点が大きな違いです。ここまで変形した結果を使って、元の問題を解いてみましょう。

点 \(P = (x, y)\) について、 \(N\) 個の点 \((x_i, y_i)\) のうち最もマンハッタン距離の大きい点を求めたいのでした。

初めに、各点について、 \(X_i = (x_i + y_i), Y_i = (x_i - y_i)\) を求めておきます。\(P\) についても、\(X = x + y, Y = x - y\) として求めておきましょう。

例えばすべての \(i\) に対する \(X - X_i\) の最大値を求めたいときは、 全ての \(i\) に対する \(X_i\) の 最小値を求めておけば求めることができます。同様に、適切に \(X_i\) や \(Y_i\) の最大値、最小値を記録しておくことで、 \((X- X_i, X_i - X, Y- Y_i, Y_i - Y)\) の値を高速に求めることができます。あとは、この4通りの値の最大値を求めれば、それが点 \(P\) から最も遠い点までの距離です。

この解法では、途中で \(X = x + y, Y = x - y\) という置き換えを使うことで見通しを良くしていました。このように、適切に変数を置き替えることで、うまく 2種類の変数が分離した形にできることがあります。

「マンハッタン距離は 45度回転」は、典型キーワードとして覚えておいてよいでしょう。

おまけ: 高次元の場合

\(3\) 次元以上の場合、 \(45\) 度回転する方法ではうまくいきません。絶対値を \(\max\) に置き替えたときの式

\( \mathrm{dist}(P_1, P_2) = \max(x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1, x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1) \)

は、高次元でも同じように計算できます。\(D\) 次元だと、 \(2^D\) 通りの式が出てくるので、符号に注意しながら全通り求めることで、 \(O(2^D)\) の計算量である点から最も遠い点までの距離を求めることができます。

問題例: https://yukicoder.me/problems/no/2261