OI - Choose a Square | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Choose a Square

发表于 分类于 Valine：

其实不算太难，这场应该是有可能可以 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，欢迎提问~