座標 \((x,y)\) と \(i\) 番目のクリスマスツリー \((X_i,Y_i)\) のマンハッタン距離は \(|x-X_i|+|y-Y_i|\) と表すことができます。この式を変形すると、以下のようになります。

\( \begin{aligned} &\phantom{=}|x-X_i|+|y-Y_i|\\ &=\max\lbrace x-X_i,-(x-X_i) \rbrace+\max\lbrace y-Y_i,-(y-Y_i) \rbrace \\ &= \max\lbrace x-X_i+y-Y_i,x-X_i-y+Y_i,-x+X_i+y-Y_i,-x+X_i-y+Y_i\rbrace \\ &= \max\lbrace \max\lbrace (x+y)-(X_i+Y_i),-(x+y)+(X_i+Y_i) \rbrace,\max\lbrace (x-y)-(X_i-Y_i),-(x-y)+(X_i-Y_i) \rbrace \rbrace \\ &=\max \lbrace \left|(x+y)-(X_i+Y_i)\right|,\left|(x-y)-(X_i-Y_i)\right| \rbrace \end{aligned} \)

この式変形はマンハッタン距離の \(45\) 度回転という名前で広く知られています。

この式変形により、クエリ \(2\) で求める値は

\( \begin{aligned} &\phantom{=}\max_{L\le i\le R} (|x-X_i|+|y-Y_i|)\\ &=\max_{L\le i\le R}\max \lbrace \left|(x+y)-(X_i+Y_i)\right|,\left|(x-y)-(X_i-Y_i)\right| \rbrace\\ &=\max \left\lbrace \max_{L\le i\le R} \left|(x+y)-(X_i+Y_i)\right|, \max_{L\le i\le R} \left|(x-y)-(X_i-Y_i)\right|\right\rbrace\\ \end{aligned} \)

となります。 \(U_i=X_i+Y_i,V_i=X_i-Y_i,u=x+y,v=x-y\) とすると、 \(U,V,u,v\) は全て入力から決まり、その中で \(\displaystyle \max \left\lbrace \max_{L\le i\le R} \left|u-U_i\right|, \max_{L\le i\le R} \left|v-V_i\right|\right\rbrace\) を求める問題と捉えることができます。

ここで、 \(|u-U_i|\) を最大にする \(i\) は \(U_i\) を最小または最大にします。したがって、 \(L\) 項目から \(R\) 項目までの \(U_i\) の最小値・最大値を高速に計算することができればよく、これは Segment Tree を用いることでクエリ毎に \(O(\log N)\) 時間で達成することができます。 \(V_i\) についても同様です。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+Q\log N)\) です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>

template <typename T>
bool chmax(T &x, T y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

long op_min(long x, long y) { return min(x, y); }
long op_max(long x, long y) { return max(x, y); }
constexpr long INF = 1e18;
long e_min() { return INF; }
long e_max() { return -INF; }

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n, que;
	cin >> n >> que;
	vector<long> u(n), v(n);
	for (int i = 0; i < n; i++) {
		long x, y;
		cin >> x >> y;
		u[i] = x + y, v[i] = x - y;
	}
	atcoder::segtree<long, op_min, e_min> u_min(u), v_min(v);
	atcoder::segtree<long, op_max, e_max> u_max(u), v_max(v);
	while (que--) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int i;
			long x, y;
			cin >> i >> x >> y;
			i--;
			u[i] = x + y, v[i] = x - y;
			u_min.set(i, u[i]);
			v_min.set(i, v[i]);
			u_max.set(i, u[i]);
			v_max.set(i, v[i]);
		} else {
			int l, r;
			long x, y;
			cin >> l >> r >> x >> y;
			l--;
			long u0 = x + y, v0 = x - y;
			long ans = 0;
			chmax(ans, abs(u0 - u_min.prod(l, r)));
			chmax(ans, abs(v0 - v_min.prod(l, r)));
			chmax(ans, abs(u0 - u_max.prod(l, r)));
			chmax(ans, abs(v0 - v_max.prod(l, r)));
			cout << ans << '\n';
		}
	}
}