既然没有题解我就自己写一篇吧

参照了claris的题解。

这道题一拿到时，看了下n，1000000，下意识去分析单调栈，但怒调半小时样例都没过（太弱了），开始推结论。

很明显为了让周长更短，矩形应该集中在更小的区域内。

经过一波画图和推导后，我们发现最优情况一定是所有石头翻到直线y=x同侧。

本人并不会很严谨的证明，但在这给出自己的分析思路：分析每个点带来的周长变化，按照矩形沿x轴方向长还是y轴方向长分两类讨论，方便起见我们假设这个矩形在y=x下方，翻过去后改动的周长就是当前点沿y轴方向到直线距离和翻过去的点沿x轴方向到直线的距离（距离不算上矩阵内的长度）之差，我们发现这肯定会让答案变大。

如果有大佬发现错误或有严谨证明，希望在评论区指出。

因为矩形的四个点可以同时被点的x值和y值更新，所以分四种情况讨论。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const ll N=1e6+10,inf=1e18;
ll n,m[N],x[N],y[N],v[N],fin[N],lx=inf,rx,ly=inf,ry,now,ans=inf,i,j;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void calc(ll lx,ll rx,ll ly,ll ry){
	for(now=0,i=1;i<=n;i++){
		if(lx<=x[i]&&x[i]<=rx&&ly<=y[i]&&ry>=y[i]){v[i]=0;continue;}
		if(lx<=y[i]&&y[i]<=rx&&ly<=x[i]&&ry>=x[i]){v[i]=1;now+=m[i];}
		else return;
	}
	if(now<ans){ans=now;for(i=1;i<=n;i++)fin[i]=v[i];}
}
int main(){
	n=read();
	for(i=1;i<=n;i++){
		x[i]=read(),y[i]=read(),m[i]=read();
		if(x[i]<=y[i]){
			lx=min(lx,x[i]);rx=max(rx,x[i]);
			ly=min(ly,y[i]);ry=max(ry,y[i]);
		}
		else{
			lx=min(lx,y[i]);rx=max(rx,y[i]);
			ly=min(ly,x[i]);ry=max(ry,x[i]);
		}
	}
	printf("%lld ",2*(rx+ry-lx-ly));
	calc(lx,rx,ly,ry);calc(lx,ry,ly,rx);calc(ly,rx,lx,ry);calc(ly,ry,lx,rx);
	printf("%lld\n",ans);
	for(i=1;i<=n;i++)printf("%lld",fin[i]);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10, inf=1e9;
LL n, ans, sum, x[N], y[N], m[N], v[N], st[N];
void solve(LL lx, LL rx, LL ly, LL ry) {
    sum=0;
    for(int i=1;i<=n;i++) {
        if(lx <= x[i] && rx >= x[i] && ly <= y[i] && ry >= y[i]) {v[i]=0; continue;} //如果不在范围内就不管 
        if(lx <= y[i] && rx >= y[i] && ly <= x[i] && ry >= x[i]) {v[i]=1; sum+=m[i];} //如果在则加上 
        else return ; //不可能更优，排除 
    }
    if(sum < ans) {ans=sum; for(int i=1;i<=n;i++) st[i]=v[i];} //更新答案 
}
int main() {
    scanf("%d", &n);
    LL lx=inf, rx=0, ly=inf, ry=0;
    //为了使lx!=ly,rx!=ry,我们定义min(x[i],y[i])为横坐标，max(x[i], y[i])为纵坐标 
    //即lx<ly, rx<ry 
    //lx表示最小的横坐标，ly表示最大的纵坐标中最小的 (rx,ry同理)
    //即求出边界的4个点
    //从右至左，上至下依次为
    //(lx, rx), (lx, ry)
    //(ly, rx), (ly, ry) 
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d", &x[i], &y[i], &m[i]);
        lx=min(lx, min(x[i], y[i])), rx=max(rx, min(x[i], y[i]));
        ly=min(ly, max(x[i], y[i])), ry=max(ry, max(x[i], y[i]));
    }
    printf("%lld ", 2*(rx+ry-lx-ly));
    ans=inf;
    //尝试是否可以翻折  
    //对角线逐一对应 （考虑将所有点翻折到y=x的一边） 
    solve(lx, rx, ly, ry); 
    solve(lx, ry, ly, rx);
    solve(ly, rx, lx, ry); 
    solve(ly, ry, lx, rx);
    printf("%lld\n", ans);
    for(int i=1;i<=n;i++) printf("%lld", st[i]);
    return 0;
}