k-d tree 求码风改良以及卡常

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
const int inf=1e18+10,R=1e9+5;
struct ms{
	int x[3],l[3],r[3];
	bool e;
	int ls,rs,sz;
	int v[4],t[4];
	// a+b a-b -a+b -a-b
	void init(){
		sz=1;
		int a=x[1],b=x[2];
		v[0]=a+b;
		v[1]=a-b;
		v[2]=-a+b;
		v[3]=-a-b;
	}
}f[N<<2];
int cnt;
struct kd{
	int b[N],rt[N],cs;
	void push_up(int u){
		int ls=f[u].ls;
		int rs=f[u].rs;
		f[u].sz=f[ls].sz+f[rs].sz+(!f[u].e);
		for(int j=0;j<4;j++){
			if(!f[u].e) f[u].t[j]=f[u].v[j];
			else f[u].t[j]=-inf; 
		}
		for(int k=0;k<=2;k++){
			if(!f[u].e){
				f[u].l[k]=f[u].x[k];
				f[u].r[k]=f[u].x[k];
			}
			else{
				f[u].l[k]=inf;
				f[u].r[k]=-inf;
			}
		}
		auto rep=[&](int v){
			if(!f[v].sz) return;
			for(int j=0;j<4;j++){
				f[u].t[j]=max(f[u].t[j],f[v].t[j]);
			}
			for(int k=0;k<=2;k++){
				f[u].l[k]=min(f[u].l[k],f[v].l[k]);
				f[u].r[k]=max(f[u].r[k],f[v].r[k]);
			}
		};
		rep(ls);
		rep(rs);
	}
	int build(int l,int r,int dep){
		int m=(l+r)>>1;
		nth_element(b+l,b+m,b+r+1,[&](int c,int d){
			return f[c].x[dep]<f[d].x[dep];
		});
		int u=b[m];
		if(l<m) f[u].ls=build(l,m-1,(dep+1)%3);
		if(m<r) f[u].rs=build(m+1,r,(dep+1)%3);
		push_up(u);
		return u;
	}
	void append(int &u){
		if(!u) return;
		b[++cs]=u;
		append(f[u].ls);
		append(f[u].rs);
		u=0;
	}
	void ins(int u){
		cs=0;
		b[++cs]=u;
		for(int i=0;;i++){
			if(rt[i]){
				append(rt[i]);
			}
			else{
				rt[i]=build(1,cs,0);
				return;
			}
		}
	}
	bool c_in(int x,int y){// whether x is in y
		for(int k=0;k<=2;k++){
			if(!(f[y].l[k]<=f[x].l[k]&&f[x].r[k]<=f[y].r[k])) return 0;
		}
		return 1;
	}
	bool c_ex(int x,int y){// whether x is out of y
		for(int k=0;k<=2;k++){
			if(f[x].l[k]>f[y].r[k]||f[y].l[k]>f[x].r[k]) return 1;
		}
		return 0;
	}
	bool c_pos(int x,int y){// whether x can be contained in y
		for(int k=0;k<=2;k++){
			if(!(f[y].l[k]<=f[x].x[k]&&f[x].x[k]<=f[y].r[k])) return 0;
		}
		return 1;
	}
	int que(int u,int k,int pos){
		if(!u) return -inf;
		if(c_in(k,u)){
			return f[u].t[pos];
		}
		if(c_ex(k,u)){
			return -inf;
		}
		int res=-inf;
		if(!f[u].e&&c_pos(u,k)){
			res=max(res,f[u].v[pos]);
		}
		res=max({res,que(f[u].ls,k,pos),que(f[u].rs,k,pos)});
		return res;
	}
	int que_f(int k,int pos){
		int res=-inf;
		for(int i=0;i<=20;i++){
			res=max(res,que(rt[i],k,pos));
		}
		return res;
	}
	bool dfs(int u,int k){
		if(!u) return 0;
		if(!c_pos(k,u)) return 0;
		int ok=1;
		for(int j=0;j<=2;j++){
			if(f[u].x[j]!=f[k].x[j]){
				ok=0;
				break;
			}
		}
		if(ok){
			f[u].e=1;
			push_up(u);
			return 1;
		}
		int r=0;
		r|=dfs(f[u].ls,k);
		r|=dfs(f[u].rs,k);
		push_up(u);
		return r;
	}
	void del(int k){
		for(int i=0;i<=20;i++){
			if(dfs(rt[i],k)) return;
		}
	}
}t;
int n,q,a[N],b[N],g[N];
void nw(int i){
	g[i]=++cnt;
	f[cnt].x[0]=i;
	f[cnt].x[1]=a[i];
	f[cnt].x[2]=b[i];
	f[cnt].init();
}
void nq(int l0,int r0,int l1,int r1,int l2,int r2){
	++cnt;
	f[cnt].l[0]=l0;
	f[cnt].l[1]=l1;
	f[cnt].l[2]=l2;
	f[cnt].r[0]=r0;
	f[cnt].r[1]=r1;
	f[cnt].r[2]=r2;
}
signed main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		nw(i);
		t.ins(cnt);
	}
	while(q--){
		int op,i,l,r,x,y;
		cin>>op;
		if(op==1){
			cin>>i>>x>>y;
			t.del(g[i]);
			a[i]=x;
			b[i]=y;
			nw(i);
			t.ins(cnt);
		}
		else{
			cin>>l>>r>>x>>y;
			nq(l,r,x,R,y,R);
			int w0=t.que_f(cnt,0);
			nq(l,r,x,R,-R,y);
			int w1=t.que_f(cnt,1);
			nq(l,r,-R,x,y,R);
			int w2=t.que_f(cnt,2);
			nq(l,r,-R,x,-R,y);
			int w3=t.que_f(cnt,3);
			int ans0=w0-x-y;
			int ans1=w1-x+y;
			int ans2=w2+x-y;
			int ans3=w3+x+y;
			int res=max({ans0,ans1,ans2,ans3});
			cout<<res<<"\n"; 
		}
	}
}