The Manhattan distance between coordinates \((x,y)\) and the \(i\)-th Christmas tree at \((X_i,Y_i)\) can be represented as \(|x-X_i|+|y-Y_i|\). This can be deformed as follows:

\( \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} \)

This is a widely known trick when considering Manhattan distance: we can regard that we rotated the plane by \(45\) degrees.

By the equation above, the value asked in query \(2\) is:

\( \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} \)

If we define \(U_i=X_i+Y_i,V_i=X_i-Y_i,u=x+y,v=x-y\), these values are simply determined by the input, and we can reinterpret the problem as asking \(\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\).

Here, if \(i\) maximizes \(|u-U_i|\), then \(U_i\) is either at the maximum or the minimum. Therefore, it is sufficient to find the minimum and maximum value of \(U_i\) among the \(L\)-th through \(R\)-th term, which can be achieved by a Segment Tree in \(O(\log N)\) time. Same goes for \(V_i\).

The problem can be solved by appropriately implementing this algorithm. The computational complexity is \(O(N+Q\log N)\).

Sample code (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';
		}
	}
}