CF1221F Choose a Square

upd：句末加了句号（。

毒瘤扫描线/tuu。

题意说的很清楚了，然后注意一下 正方形边长可以是 0。

我们知道一个点 $(x,y)$ 在正方形 $(l,l)\rightarrow(r,r)$ 内时有 $l\leq x,y\leq r$。

然后考虑一条直线 $y=x$，我们将其下的点全部沿它对称翻到上面去这样就有 $x\leq y$，连接 $(x,y)$ 和 $(y,x)$ 得到一条权值为 $c$ 的线段，这样就将题意化为被正方形包含的边的边权和与正方形边长的差。

具体来说，就是求

$\sum\limits_{i\in[1,n],l\leq l_i,r_i\leq r}c_i-r+l$

的最大值。

$l$ 不变，就只用求前面那一坨的最大值了。

这样就可以扫描线了，用线段树维护。

设离散化后有 $m$ 个点，从后往前把线加进去，显然有 $l_i>l$，那么只要让 $r_i<r$ 即可，将 $[r_i,m]+c$，查询 $[i,m]$。

然后维护一下最大值，位置即可，注意最大值小于 0 时要特判一下即可。

code:

// Problem: CF1221F Choose a Square
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1221F
// Memory Limit: 250 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
#define pii pair<int,int>
using namespace std;
const int N=1e6+10,inf=1e13;
int n,tag[N<<2];
#define s first
#define id second
pii t[N<<2];
struct Node{
	int x,y,c;
}a[N];
vector<int>v;
vector<pii>g[N];
namespace tree{
	#define ls k<<1
	#define rs k<<1|1
	#define mid ((l+r)>>1)
	#define pushup(k)t[k]=make_pair(max(t[ls].s,t[rs].s),t[ls].s<t[rs].s?t[rs].id:t[ls].id)
	inl void pushdown(int k,int l,int r){
		if(!tag[k])return ;
		tag[ls]+=tag[k];tag[rs]+=tag[k];
		t[ls].s+=tag[k];t[rs].s+=tag[k];
		tag[k]=0;
	}
	inl void build(int k,int l,int r){
		if(l==r){t[k]=make_pair(-v[l-1],l);return;}
		build(ls,l,mid);build(rs,mid+1,r);pushup(k);
	}
	inl void update(int k,int l,int r,int x,int y,int v){
		if(x>r||y<l)return ;
		if(x<=l&&y>=r){tag[k]+=v;t[k].s+=v;return ;}
		pushdown(k,l,r);update(ls,l,mid,x,y,v);update(rs,mid+1,r,x,y,v);pushup(k);
	}
	pii query(int k,int l,int r,int x,int y){
		if(x>r||y<l)return make_pair(-inf,-inf);
		if(x<=l&&y>=r)return t[k];
		pushdown(k,l,r);
		return max(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
	}
}
using namespace tree;
signed main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	rep(i,1,n){
		int x,y,c;cin>>x>>y>>c;
		v.push_back(x);v.push_back(y);a[i]=(Node){min(x,y),max(x,y),c};
	}
	int m=0;
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	rep(i,1,n){
		int x=lower_bound(v.begin(),v.end(),a[i].x)-v.begin()+1,y=lower_bound(v.begin(),v.end(),a[i].y)-v.begin()+1;
		m=max(m,y);
		g[x].push_back(make_pair(y,a[i].c));
	}
	build(1,1,m);
	int ans=-inf,l,r;
	pre(i,m,1){
		rep(j,0,g[i].size()-1){
			pii tmp=g[i][j];
			update(1,1,m,tmp.first,m,tmp.second);
		}
		pii tmp=query(1,1,m,i,m);
		tmp.first+=v[i-1];
		if(tmp.first>ans){
			ans=tmp.first;
			l=v[i-1],r=v[tmp.second-1];
		}
	}
	if(ans<0)ans=0,l=r=v[m-1]+1;
	cout<<ans<<'\n'<<l<<' '<<l<<' '<<r<<' '<<r;
}