The Kouga Ninja Scrolls（2018沈阳现场E+切比雪夫距离+线段树维护最大次大最小次小）

The Kouga Ninja Scrolls

这题可真暴力呀！曼哈顿距离转成切比雪夫距离后大力线段树搞即可！第一次把线段树封装一下，为了 $x,y$x,y两个坐标不用写两棵线段树，也是第一次把 $push$push_ $up$up写成结构体 $merge$merge形式，为了方便query时的区间合并。而且写好后(赛后)1A，刺激！！！

题意：

给定二维平面上 $n$n个点（编号 $1$1~ $n$n），以及每个点的颜色（帮派），三种操作：

1. $op1:$op1:将第 $i$i个点的移动到另一个位置
2. $op2:$op2:改变第 $i$i个点的颜色（帮派）
3. $op3:$op3:询问编号属于 $[l,r]$[l,r]的点中曼哈顿距离的最大值（要求选定最远点对颜色不同）

思路：

1. 看见曼哈顿距离最大值，尽可能往切比雪夫距离上面想。比如这题，将距离转化后，我们只需要分别考虑 $x$x距离最大值和 $y$y距离最大值即可；
2. 然后就是如何分别求这两个最大距离，容易想到利用坐标的区间最大值和区间最小值，相减即是区间最大值啦！
3. 但题目有个限制，也就是大幅度增加此题码量的地方！最大距离点对颜色不能相同，那就只能再分别维护一个坐标次大值和坐标次小值（且颜色要与最大次大不同），这样当最大最小的两个点颜色相同时，就把其中一个换成次一点的。
4. 那么，思路就是如此了，代码码起来也是异常舒服！

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline ll read() {ll x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, m;
ll x[maxn], y[maxn], belong[maxn];

struct P{
    ll m[4]; int b[4];
    void clear() {
        memset(m,0,sizeof(m));
        memset(b,0,sizeof(b));
    }
    P() { clear(); }
    friend P merge(const P &c, P const &b) {//第一次写成结构体合并的形式，真的舒服
        P a=c;
        if(b.b[0]) {
            if(!a.b[0]||b.m[0]>=a.m[0]) {
                if(!a.b[0]) a.m[0]=b.m[0], a.b[0]=b.b[0];
                else if(b.b[0]!=a.b[0]) {
                    swap(a.m[0],a.m[1]); swap(a.b[0],a.b[1]);
                    a.m[0]=b.m[0], a.b[0]=b.b[0];
                }
                else if(b.m[0]>a.m[0]) a.m[0]=b.m[0];
            }
            else if(b.b[0]!=a.b[0]&&(!a.b[1]||b.m[0]>a.m[1])) {
                a.m[1]=b.m[0], a.b[1]=b.b[0];
            }
        }
        if(b.b[1]) {
            if(!a.b[0]||b.m[1]>=a.m[0]) {
                if(!a.b[0]) a.m[0]=b.m[1], a.b[0]=b.b[1];
                else if(b.b[1]!=a.b[0]) {
                    swap(a.m[0],a.m[1]); swap(a.b[0],a.b[1]);
                    a.m[0]=b.m[1], a.b[0]=b.b[1];
                }
                else if(b.m[1]>a.m[0]) a.m[0]=b.m[1];
            }
            else if(b.b[1]!=a.b[0]&&(!a.b[1]||b.m[1]>a.m[1])) {
                a.m[1]=b.m[1], a.b[1]=b.b[1];
            }
        }
        if(b.b[3]) {
            if(!a.b[3]||b.m[3]<=a.m[3]) {
                if(!a.b[3]) a.m[3]=b.m[3], a.b[3]=b.b[3];
                else if(b.b[3]!=a.b[3]) {
                    swap(a.m[3],a.m[2]); swap(a.b[3],a.b[2]);
                    a.m[3]=b.m[3], a.b[3]=b.b[3];
                }
                else if(b.m[3]<a.m[3]) a.m[3]=b.m[3];
            }
            else if(b.b[3]!=a.b[3]&&(!a.b[2]||b.m[3]<a.m[2])) {
                a.m[2]=b.m[3], a.b[2]=b.b[3];
            }
        }
        if(b.b[2]) {
            if(!a.b[3]||b.m[2]<=a.m[3]) {
                if(!a.b[3]) a.m[3]=b.m[2], a.b[3]=b.b[2];
                else if(b.b[2]!=a.b[3]) {
                    swap(a.m[3],a.m[2]); swap(a.b[3],a.b[2]);
                    a.m[3]=b.m[2], a.b[3]=b.b[2];
                }
                else if(b.m[2]<a.m[3]) a.m[3]=b.m[2];
            }
            else if(b.b[2]!=a.b[3]&&(!a.b[2]||b.m[2]<a.m[2])) {
                a.m[2]=b.m[2], a.b[2]=b.b[2];
            }
        }
        return a;
    }
};

struct SegmentTree{//第一次把线段树给封装了，也是真的舒服！！！
    P node[maxn<<2];

    void build(int l, int r, int now) {
        node[now].clear();
        if(l==r) return;
        int m=(l+r)/2;
        build(l,m,now<<1); build(m+1,r,now<<1|1);
    }

    void update(int x, ll d, int l, int r, int now) {
        if(l==r) {
            node[now].m[0]=node[now].m[3]=d;
            node[now].b[0]=node[now].b[3]=belong[x];
            return;
        }
        int m=(l+r)/2;
        if(x<=m) update(x,d,l,m,now<<1);
        else update(x,d,m+1,r,now<<1|1);
        node[now]=merge(node[now<<1],node[now<<1|1]);
    }

    P query(int x, int y, int l, int r, int now) {
        if(x<=l&&r<=y) return node[now];
        int m=(l+r)/2;
        P ans;
        if(x<=m) ans=merge(ans,query(x,y,l,m,now<<1));
        if(y>m) ans=merge(ans,query(x,y,m+1,r,now<<1|1));
        return ans;
    }

    ll solve(int x, int y) {
        P ans=query(x,y,1,n,1);
        ll res=-2e18;
        if(!ans.b[0]||!ans.b[3]) return 0;
        if(ans.b[0]==ans.b[3]) {
            if(ans.b[2]) res=max(res,ans.m[0]-ans.m[2]);
            if(ans.b[1]) res=max(res,ans.m[1]-ans.m[3]);
        }
        else res=ans.m[0]-ans.m[3];
        if(res<-1e18) return 0;
        return res;
    }
}sx, sy;

int main() {
    int T=read(); int t=0;
    while(T--) {
        printf("Case #%d:\n", ++t);
        n=read(), m=read();
        sx.build(1,n,1); sy.build(1,n,1);
        for(int i=1; i<=n; ++i) {
            ll x=read(), y=read(); belong[i]=read();
            ::x[i]=x+y, ::y[i]=x-y;
            sx.update(i,::x[i],1,n,1);
            sy.update(i,::y[i],1,n,1);
        }
        for(int i=1; i<=m; ++i) {
            int op=read();
            if(op==1) {
                int k=read(); ll dx=read(), dy=read();
                x[k]+=dx+dy; y[k]+=dx-dy;
                sx.update(k,x[k],1,n,1);
                sy.update(k,y[k],1,n,1);
            }
            else if(op==2) {
                int k=read(), c=read();
                belong[k]=c;
                sx.update(k,x[k],1,n,1);
                sy.update(k,y[k],1,n,1);
            }
            else if(op==3) {
                int l=read(), r=read();
                printf("%lld\n", max(sx.solve(l,r),sy.solve(l,r)));
            }
        }
    }
}