Gym

题意：有n个忍者（编号为1-n），每个忍者有三个属性：横坐标x，纵坐标y，所属门派c，要求支持三种操作：

1.改变第k个忍者的位置

2.改变第k个忍者的门派

3.查询编号为[l,r]之间的忍者中，所属门派不同的两个忍者的最大曼哈顿距离

通过曼哈顿距离变换，将每个忍者的横坐标和纵坐标拆成x+y和x-y，两种情况分别用线段树维护区间最大值，最小值，最大值和最小值所属门派，以及门派不同的次大值及次小值（非严格），查询时分两种情况：

1.最大值和最小值门派不同：答案为最大值-最小值

2.最大值和最小值门派相同：答案为max(最大值-次小值，次大值-最小值)

两种情况分别讨论一下，然后取个最大值即可。

无解的情况需要特判一下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,inf=0x3f3f3f3f3f3f3f3fll;
ll n,m,X[N],Y[N],C[N],ka;
struct D {ll mx,smx,mi,smi,umx,umi;} tr[N<<2][2];
D operator+(const D& a,const D& b) {
    if(a.mx==~inf)return b;
    if(b.mx==~inf)return a;
    D c;
    c.mx=max(a.mx,b.mx);
    c.mi=min(a.mi,b.mi);
    c.umx=c.mx==a.mx?a.umx:b.umx;
    c.smx=max(a.smx,b.smx);
    if(a.umx!=b.umx)c.smx=max(c.smx,min(a.mx,b.mx));
    c.umi=c.mi==a.mi?a.umi:b.umi;
    c.smi=min(a.smi,b.smi);
    if(a.umi!=b.umi)c.smi=min(c.smi,max(a.mi,b.mi));
    return c;
}
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
void pu(ll u) {tr[u][0]=tr[ls][0]+tr[rs][0],tr[u][1]=tr[ls][1]+tr[rs][1];}
void build(ll u=1,ll l=1,ll r=n) {
    if(l==r) {
        tr[u][0]= {X[l]+Y[l],~inf,X[l]+Y[l],inf,C[l],C[l]};
        tr[u][1]= {X[l]-Y[l],~inf,X[l]-Y[l],inf,C[l],C[l]};
        return;
    }
    build(ls,l,mid),build(rs,mid+1,r),pu(u);
}
void upd(ll p,ll x,ll y,ll c,ll u=1,ll l=1,ll r=n) {
    if(l==r) {
        tr[u][0]= {x+y,~inf,x+y,inf,c,c};
        tr[u][1]= {x-y,~inf,x-y,inf,c,c};
        return;
    }
    p<=mid?upd(p,x,y,c,ls,l,mid):upd(p,x,y,c,rs,mid+1,r);
    pu(u);
}
D qry(ll L,ll R,ll f,ll u=1,ll l=1,ll r=n) {
    if(l>=L&&r<=R)return tr[u][f];
    if(l>R||r<L)return {~inf};
    return qry(L,R,f,ls,l,mid)+qry(L,R,f,rs,mid+1,r);
}
int main() {
    ll T;
    for(scanf("%lld",&T); T--;) {
        printf("Case #%lld:
",++ka);
        scanf("%lld%lld",&n,&m);
        for(ll i=1; i<=n; ++i)scanf("%lld%lld%lld",&X[i],&Y[i],&C[i]);
        build();
        while(m--) {
            ll f,l,r,k,c,x,y;
            scanf("%lld",&f);
            if(f==1)scanf("%lld%lld%lld",&k,&x,&y),upd(k,X[k]+=x,Y[k]+=y,C[k]);
            else if(f==2)scanf("%lld%lld",&k,&c),upd(k,X[k],Y[k],C[k]=c);
            else if(f==3) {
                scanf("%lld%lld",&l,&r);
                D a=qry(l,r,0),b=qry(l,r,1);
                ll x=a.umx==a.umi?max(a.mx-a.smi,a.smx-a.mi):a.mx-a.mi;
                ll y=b.umx==b.umi?max(b.mx-b.smi,b.smx-b.mi):b.mx-b.mi;
                printf("%lld
",a.smx==~inf?0:max(x,y));
            }
        }
    }
    return 0;
}