Gym - 101955E The Kouga Ninja Scrolls (曼哈顿距离变换+线段树)

题意：有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+,inf=0x3f3f3f3f3f3f3f3fll;

 ll n,m,X[N],Y[N],C[N],ka;

 struct D {ll mx,smx,mi,smi,umx,umi;} tr[N<<][];

 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][]=tr[ls][]+tr[rs][],tr[u][]=tr[ls][]+tr[rs][];}

 void build(ll u=,ll l=,ll r=n) {

     if(l==r) {

         tr[u][]= {X[l]+Y[l],~inf,X[l]+Y[l],inf,C[l],C[l]};

         tr[u][]= {X[l]-Y[l],~inf,X[l]-Y[l],inf,C[l],C[l]};

         return;

     }

     build(ls,l,mid),build(rs,mid+,r),pu(u);

 }

 void upd(ll p,ll x,ll y,ll c,ll u=,ll l=,ll r=n) {

     if(l==r) {

         tr[u][]= {x+y,~inf,x+y,inf,c,c};

         tr[u][]= {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+,r);

     pu(u);

 }

 D qry(ll L,ll R,ll f,ll u=,ll l=,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+,r);

 }

 int main() {

     ll T;

     for(scanf("%lld",&T); T--;) {

         printf("Case #%lld:\n",++ka);

         scanf("%lld%lld",&n,&m);

         for(ll i=; 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==)scanf("%lld%lld%lld",&k,&x,&y),upd(k,X[k]+=x,Y[k]+=y,C[k]);

             else if(f==)scanf("%lld%lld",&k,&c),upd(k,X[k],Y[k],C[k]=c);

             else if(f==) {

                 scanf("%lld%lld",&l,&r);

                 D a=qry(l,r,),b=qry(l,r,);

                 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\n",a.smx==~inf?:max(x,y));

             }

         }

     }

     return ;

 }