官方题解 | Square

H. Square

Subtask 20 pt

不断枚举 $3$ 个不同颜色的点，时间复杂度 $O(N^3)$。

Subtask 60 pt

按 $x$ 递增枚举前两个点，那么第三个点的情况被这两个点的 $y$ 坐标分为三部分，分别记录 $x$ 的后缀这三部分的 $x,(x+y),(x-y)$ 最大值即可快速计算，离散化使支持区间查询，这里因为 $N$ 比较小可以暴力更新，时间复杂度 $O(N^2)$。在实现时考虑对颜色进行置换，复杂度为 $O(N^2 \times 6)$。

Subtask 100 pt

采用扫描线、二位数点。

由于 $N$ 较大，暴力更新会超时，采用树状数组或线段树的解法更新。

经过分析可以发现三个点的位置可能是：

1. 两个点在矩形的邻边上且相对，一个点在矩形内部。（共存在 $6$ 组置换，两个边上的点控制了四边的缩小）
2. 两个点在矩形的边上且相边相邻，一个点在矩形邻边上。（共存在 $4$ 组置换，三个点控制了四边的缩小）

首先对于颜色进行排列置换，并对坐标进行四个象限的变换。这样我们可以从左到右钦定颜色加入的顺序。

经过前面的变换，我们按照 $x$ 坐标升序，我们发现本质不同的三个点形态只有 $y$​ 递增，或者先增再减。

第一种可以直接开两个树状数组，把第一个点的 $−x−y$​ 扔进第一个树状数组，然后由第二点查询传递到第二颗树状数组（这里是为了保证有这样一个点处在中间）。

第二种情况我们可以按顺序加入前两个点，并用扫描线采用二位数点找出第三个点，在线段树上直接赋值（一个对后缀赋值，一个对前缀赋值，那么他们中间的点一定可以两个信息都接受到，并且合并这两个信息得到答案），最终在第三个点的 $y$ 坐标处进行单点查询，需要把 $x$ 的差加上，线段树里存的是 $y$ 的差值和第一个点的 $。。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=2e5+10,inf=1e9+10; 
ll n,tx,ty;
ll rrx[N],rry[N],rrc[N];
ll x[N],y[N],rc[N],c[N];
ll mxx=0,mxy=0;
ll dx[N],dy[N],rx[N],ry[N],px[N],py[N];
ll d[4]={0,1,2,3};
#define lowbit(i) (i&(-i))
struct szmin{
	ll c[N];
	inline void clear(){for(int i=1;i<=ty;i++)c[i]=inf;return ;}
	inline void add(ll x,ll y){
		for(int i=x;i<=ty;i+=lowbit(i))c[i]=min(c[i],y);
		return ;
	}inline ll ask(ll x){ll an=inf;for(int i=x;i;i-=lowbit(i))an=min(an,c[i]);return an;}
}o,p; 
inline bool cmpx(ll px,ll py){if(x[px]!=x[py])return x[px]<x[py];return y[px]<y[py];}
ll ans=inf;
inline void s1(){
	o.clear();p.clear();
	for(int t=1;t<=n;t++){
		ll i=px[t];if(c[i]==0){
			o.add(dy[i],-x[i]-y[i]);
		}if(c[i]==1){
			p.add(dy[i],o.ask(dy[i]));
		}if(c[i]==2){
			ans=min(ans,x[i]+y[i]+p.ask(dy[i]));
		}
	}return ;
}
ll val[N<<2],t1[N<<2],t2[N<<2];
inline void build(ll o,ll l,ll r){
	val[o]=t1[o]=t2[o]=inf;if(l==r)return ;
	ll mid=(l+r)>>1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);
	return ;
}
inline void push1(ll o,ll x){ 
	t1[o]=min(t1[o],x);return ;
}inline void push2(ll o,ll x){
	val[o]=min(val[o],t1[o]+x);t2[o]=min(t2[o],x);return ;
}
inline void pushdown(ll o){
	if(t2[o]*2<inf)push2(o<<1,t2[o]),push2(o<<1|1,t2[o]),t2[o]=inf;if(t1[o]*2<inf)push1(o<<1,t1[o]),push1(o<<1|1,t1[o]),t1[o]=inf;
	return ;
}
inline ll ask(ll o,ll l,ll r,ll x){
	if(l==r)return val[o];
	ll mid=(l+r)>>1;pushdown(o);
	if(mid>=x)return min(val[o],ask(o<<1,l,mid,x));
	return min(val[o],ask(o<<1|1,mid+1,r,x));
}
inline void upd1(ll o,ll l,ll r,ll x,ll y,ll z){
	if(x<=l&&r<=y){push1(o,z);return ;}
	ll mid=(l+r)>>1;pushdown(o);
	if(mid>=x)upd1(o<<1,l,mid,x,y,z);
	if(mid<y)upd1(o<<1|1,mid+1,r,x,y,z);
	return ;
}
inline void upd2(ll o,ll l,ll r,ll x,ll y,ll z){
	if(x<=l&&r<=y){push2(o,z);return ;}
	ll mid=(l+r)>>1;pushdown(o);
	if(mid>=x)upd2(o<<1,l,mid,x,y,z);
	if(mid<y)upd2(o<<1|1,mid+1,r,x,y,z);
	return ;
}
inline void s2(){
	build(1,1,ty);
	for(int t=1;t<=n;t++){
		ll i=px[t];if(c[i]==0){
			upd1(1,1,ty,dy[i],ty,-x[i]-y[i]);
		}if(c[i]==1){
			upd2(1,1,ty,1,dy[i],y[i]);
		}if(c[i]==2){
			ans=min(ans,ask(1,1,ty,dy[i])+x[i]);
		}
	}return ;
}
inline void solve(){
	s1();s2();
	return ;
} 
inline void ss(ll tpx,ll tpy){
	for(int i=1;i<=n;i++){
		if(tpx==1)x[i]=rrx[i];else x[i]=mxx-rrx[i]+1;if(tpy==1)y[i]=rry[i];else y[i]=mxy-rry[i]+1;
		rc[i]=rrc[i];rx[i]=x[i];ry[i]=y[i];px[i]=i;		
	}sort(rx+1,rx+n+1);sort(ry+1,ry+n+1);tx=unique(rx+1,rx+n+1)-rx-1,ty=unique(ry+1,ry+n+1)-ry-1;
	for(int i=1;i<=n;i++)dx[i]=lower_bound(rx+1,rx+n+1,x[i])-rx;for(int i=1;i<=n;i++)dy[i]=lower_bound(ry+1,ry+n+1,y[i])-ry; 
	sort(px+1,px+n+1,cmpx);for(int i=0;i<3;i++)d[i]=i;
	while(1){
		for(int i=1;i<=n;i++)c[i]=d[rc[i]];
		solve();if(!next_permutation(d,d+3))break;
	}return ;
}
int main(){
	cin>>n;for(int i=1;i<=n;i++)cin>>rrx[i]>>rry[i]>>rrc[i],mxx=max(mxx,rrx[i]),mxy=max(mxy,rry[i]);
	ss(1,1);
	ss(1,0);
	ss(0,1);
	ss(0,0);
	cout<<ans*2;return 0;
}

时间复杂度：$O(N \log N \times 24)$