OI - Choose a Square

其实不算太难,这场应该是有可能可以 AK 的


Part1. 题面

平面直角坐标系上有 $n$ 个点,第 $i$ 个点坐标为 $(x_i,y_i)$、权值为 $v_i$。

你需要在直线 $y=x$ 上选择两个点 $(a,a),(b,b)$($a\le b$),并且以 $(a,a)$ 为左下角、$(b,b)$ 为右上角作一个正方形。得分为在这个正方形中的点的权值之和(在正方形的边上也算)减去正方形的边长(不是周长)。

求怎样选择 $a,b$ 可以使得得分最大,求最大得分以及此时的 $a,b$(任意一个)。

数据规模

  • $1\le n\le 5\times10^5$;
  • $0\le x_i,y_i\le 10^9$;
  • $-10^6\le v_i\le10^6$;
  • 要求输出的 $0\le a,b\le2\times10^9$;

Part2. 解析

扫描线的思想是把点转成能够框住它的矩形;这道题也不例外,只是转换有点奇怪。

如果点 $i$ 被正方形框住,就说明 $a\le x_i\le b$ 并且 $a\le y_i\le b$;换种写法 $a\le\min\{x_i,y_i\}\le\max\{x_i,y_i\}\le b$。

发现“能够框住点的矩形”变成了“能够框住一条线段的线段”:也就是线段 $(a,b)$ 要能够把 $(\min\{x_i,y_i\},\max\{x_i,y_i\})$ 框住。于是就变成了一维的 扫描线 ——

显然最优答案要么是什么点都不圈、框一个边长为 0 $(a=b)$ 的正方形;要么是至少有一个点在正方形的边上(否则就可以缩小正方形的边长,使得它仍然圈住已有的点,这样答案一定更优)。所以我们读入时把点 $(x_i,y_i)$ 转成 线段 $(\min\{x_i,y_i\},\max\{x_i,y_i\})$ ,然后把线段的两端点离散化一下。

所以现在就是要确定一条线段 $(a,b)$。从左到右枚举线段的右端点 $b$,那么右端点不超过 $b$ 的线段就有可能被框入 $(a,b)$ 中。我们用线段树维护:当右端点固定为 $b$ 时,左端点选在 $0$ 到 $b$ 的最大答案。所以我们可以这样实现线段树:

  1. 单点修改:如果线段 $(x,y)$ 的右端点不超过 $b$,就在线段树的 $x$ 处加上该线段的权值 $v$;
  2. 区间查询:查询在区间 $(0,b)$ 中选择一个点 $a$,线段树中 $(a,b)$ 的所有权值之和 $a$ 的最大值;这样求出的最大值再减去 $b$ 就可以得到答案了。当然还要维护选的是哪个点。

Part3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;

const int N=1e6;

#define all(x) x.begin(),x.end()

struct PEREDGE{int lef,rig,val;}edg[N+3];

int n;
vector<int> uni;
vector< pair<int,int> > ins[N+3];

struct SRETURN{
long long Vmx,Vsum;
int Vpnt;
SRETURN(long long Umx=0,long long Usum=0,int Upnt=0):Vmx(Umx),Vsum(Usum),Vpnt(Upnt){}
};
struct SEGTREE{
long long Smx[N<<2],Ssum[N<<2];
int Spnt[N<<2];
void PushUp(int u){
Ssum[u]=Ssum[u<<1]+Ssum[u<<1|1];
if(Smx[u<<1]+Ssum[u<<1|1]>Smx[u<<1|1])
Smx[u]=Smx[u<<1]+Ssum[u<<1|1],
Spnt[u]=Spnt[u<<1];
else
Smx[u]=Smx[u<<1|1],
Spnt[u]=Spnt[u<<1|1];
}
void Build(int u,int Cl,int Cr){
if(Cl==Cr){
Smx[u]=uni[Cl-1];
Ssum[u]=0;
Spnt[u]=uni[Cl-1];
return;
}
int Cm=(Cl+Cr)>>1;
Build(u<<1,Cl,Cm);Build(u<<1|1,Cm+1,Cr);
PushUp(u);
}
void Modify(int u,int Cl,int Cr,int Dp,int Vv){
if(Cl==Cr){
Smx[u]+=Vv;
Ssum[u]+=Vv;
return;
}
int Cm=(Cl+Cr)>>1;
if(Dp<=Cm) Modify(u<<1,Cl,Cm,Dp,Vv);
else Modify(u<<1|1,Cm+1,Cr,Dp,Vv);
PushUp(u);
}
SRETURN Query(int u,int Cl,int Cr,int Dd){
if(Dd<Cl) return SRETURN(-(1ll<<60),0,-1);
if(Cr<=Dd) return SRETURN(Smx[u],Ssum[u],Spnt[u]);
int Cm=(Cl+Cr)>>1;
SRETURN R1=Query(u<<1,Cl,Cm,Dd),R2=Query(u<<1|1,Cm+1,Cr,Dd),Rr;
Rr.Vsum=R1.Vsum+R2.Vsum;
if(R1.Vmx+R2.Vsum>R2.Vmx){
Rr.Vmx=R1.Vmx+R2.Vsum;
Rr.Vpnt=R1.Vpnt;
}
else{
Rr.Vmx=R2.Vmx;
Rr.Vpnt=R2.Vpnt;
}
return Rr;
}
}seg;

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int Ix,Iy,Iv;
scanf("%d%d%d",&Ix,&Iy,&Iv);
if(Ix>Iy) swap(Ix,Iy);
uni.push_back(Ix);
uni.push_back(Iy);
edg[i]=(PEREDGE){Ix,Iy,Iv};
}
sort(all(uni));
uni.erase(unique(all(uni)),uni.end());
for(int i=1;i<=n;i++){
edg[i].lef=lower_bound(all(uni),edg[i].lef)-uni.begin()+1;
edg[i].rig=lower_bound(all(uni),edg[i].rig)-uni.begin()+1;
ins[edg[i].rig].emplace_back(edg[i].lef,edg[i].val);
}
seg.Build(1,1,uni.size());
long long Uans=0;int Ul=uni.back()+1,Ur=uni.back()+1;
for(int i=1;i<=uni.size();i++){
for(auto it : ins[i])
seg.Modify(1,1,uni.size(),it.first,it.second);
SRETURN Vans=seg.Query(1,1,uni.size(),i);
Vans.Vmx-=uni[i-1];
if(Vans.Vmx>Uans){
Uans=Vans.Vmx;
Ul=Vans.Vpnt;
Ur=uni[i-1];
}
}
printf("%lld\n%d %d %d %d\n",Uans,Ul,Ul,Ur,Ur);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问~

0%