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

\[ \begin{aligned} |x - X_i| + |y - Y_i| &= \max\{x - X_i,\,-(x - X_i)\} + \max\{y - Y_i,\,-(y - Y_i)\} \\ &= \max\{x - X_i + y - Y_i,\; x - X_i - y + Y_i,\; -x + X_i + y - Y_i,\; -x + X_i - y + Y_i\} \\ \end{aligned} \]

ここから、\(-X_i-Y_i, -X_i+Y_i, +X_i-Y_i, +X_i+Y_i\) の \(4\) 本のセグ木を持つことで、\(x,y\) とうまく組み合わせることにより最大値を求めることができます。

実装例(C++)

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


template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }


using S = long long;
const S INF = 8e18;
S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }


int main(){
    int N,Q;
    cin>>N>>Q;
    segtree<S, op, e>MM(N);
    segtree<S, op, e>MP(N);
    segtree<S, op, e>PM(N);
    segtree<S, op, e>PP(N);
    for(int i=0;i<N;i++){
        int a,b;
        cin>>a>>b;
        MM.set(i,-a-b);
        MP.set(i,-a+b);
        PM.set(i,a-b);
        PP.set(i,a+b);
    }
    while(Q--){
        int t;
        cin>>t;
        if(t==1){
            int i,a,b;
            cin>>i>>a>>b;
            i--;
            MM.set(i,-a-b);
            MP.set(i,-a+b);
            PM.set(i,a-b);
            PP.set(i,a+b);
        }else{
            int l,r,x,y;
            cin>>l>>r>>x>>y;
            l--;
            ll ans=0;
            chmax(ans,x+y+MM.prod(l,r));
            chmax(ans,x-y+MP.prod(l,r));
            chmax(ans,-x+y+PM.prod(l,r));
            chmax(ans,-x-y+PP.prod(l,r));
            cout<<ans<<endl;
        }
    }
}