题意
给出(n)个带权值的点，求一个顶点在对角线上的正方形，使正方形内点权和减去边长的值最大。
(1 le n le 5 imes 10^5,0 le x_i,y_i le 10^9)
思路
进行转化，正方形((l,l)(r,r))要包含点((x,y))，即满足(l le min(x,y),r ge max(x,y))。这样我们就可以将问题转化为：给出(n)条带权线段，求一条线段，使得其完整覆盖的线段权值和减去长度最短。
枚举右端点，查询最大的后缀和加左端点，只要用线段树维护(f[i]=sum_{j=1}^n w_j[l[j]ge i]+i)。先把所有线段加入，右端点左移是减去已经超出的线段的贡献即可。
因为坐标范围较大，所以需要离散化
#include <bits/stdc++.h>
using std::pair;
using std::make_pair;
#define f first
const int N=2000005;
typedef long long ll;
typedef pair<ll,int> pli;
pli t[N<<2];
ll ans,tag[N<<2];
int x,y,b[N],n,cnt,ansl,ansr;
struct node{
int l,r,w,rr;
}a[N];
bool cmp(node x,node y){
return x.r==y.r?x.l<y.l:x.r<y.r;
}
void pushdown(int x){
if (tag[x]){
t[x<<1].f+=tag[x],tag[x<<1]+=tag[x];
t[x<<1|1].f+=tag[x],tag[x<<1|1]+=tag[x];
tag[x]=0;
}
}
void pushup(int x){
t[x]=std::max(t[x<<1],t[x<<1|1]);
t[x].f+=tag[x];
}
void build(int k,int l,int r){
if (l==r){
t[k].f=b[l];
t[k].second=b[l];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
pushup(k);
}
void modify(int k,int L,int R,int l,int r,int x){
if (L==l && R==r){
t[k].f+=x,tag[k]+=x;
return;
}
pushdown(k);
int mid=(L+R)>>1;
if (r<=mid) modify(k<<1,L,mid,l,r,x);
else if (l>mid) modify(k<<1|1,mid+1,R,l,r,x);
else{
modify(k<<1,L,mid,l,mid,x);
modify(k<<1|1,mid+1,R,mid+1,r,x);
}
pushup(k);
}
pli query(int k,int L,int R,int l,int r){
if (L==l && R==r) return t[k];
int mid=(L+R)>>1;
pushdown(k);
if (r<=mid) return query(k<<1,L,mid,l,r);
if (l>mid) return query(k<<1|1,mid+1,R,l,r);
return std::max(query(k<<1,L,mid,l,mid),query(k<<1|1,mid+1,R,mid+1,r));
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&a[i].w);
a[i].l=std::min(x,y);
a[i].r=std::max(x,y);
b[++cnt]=a[i].l,b[++cnt]=a[i].r;
}
std::sort(b+1,b+cnt+1);
cnt=std::unique(b+1,b+cnt+1)-b-1;
for (int i=1;i<=n;i++){
a[i].l=std::lower_bound(b+1,b+cnt+1,a[i].l)-b;
a[i].rr=a[i].r;
a[i].r=std::lower_bound(b+1,b+cnt+1,a[i].r)-b;
}
std::sort(a+1,a+n+1,cmp);
build(1,1,cnt);
for (int i=1;i<=n;i++) modify(1,1,cnt,1,a[i].l,a[i].w);
int i=n;
while (i>=1){
pli t=query(1,1,cnt,1,a[i].r);
if (t.first-a[i].rr>ans) ans=t.first-a[i].rr,ansl=t.second,ansr=a[i].rr;
int j=i;
while (a[j].r==a[i].r) modify(1,1,cnt,1,a[j].l,-a[j].w),j--;
i=j;
}
printf("%lld
",ans);
if (ans==0) printf("%d %d %d %d
",b[cnt]+1,b[cnt]+1,b[cnt]+1,b[cnt]+1);
else printf("%d %d %d %d
",ansl,ansl,ansr,ansr);
}
后记
开心了写个blog