ARC063 F Snuke's Coloring 2

题意

小C很喜欢二维染色问题,这天他拿来了一个$w \times h$的二维平面,初始时均为白色。然后他在上面设置了$n$个关键点$(X_i,Y_i)$,对于每个关键点他会选择进行下列操作的一个:

  • 将$x > X_i$ 的部分染成黑色。
  • 将$x < X_i$ 的部分染成黑色。
  • 将$y > Y_i$ 的部分染成黑色。
  • 将$y < Y_i$ 的部分染成黑色。

要求最大化所有操作结束之后白色部分的周长。特别地,如果没有白色部分,设其周长为0。

$n \le 2 \times 10^5$。

题解

首先,不难把题目转化为,需要找到一个面积最大的矩形,满足矩形内部没有点。

可以发现一个性质,即答案的下界为$2 \times (\max(w,h)+1)$,所以这个周长最大的矩形,一定过$x=\frac{w}{2}$或$y=\frac{h}{2}$。两种情况相似,我们只需考虑过$y= \frac{h}{2}$的情况,另一种交换一下横纵坐标即可。

首先考虑一个$O(n^2)$的做法。枚举矩形的上边界,对于每一个下边界,我们都找出他最多能到的左边界$x_L=\min\{x_i|y_i \in [y_L,y_R],x < \frac{w}{2}\}$与右边界$x_R=\max\{x_i|y_i \in [y_L,y_R],x \ge \frac{w}{2}\}$。于是我们不断chkmax即可。注意到,这个过程可以用线段树进行优化。

仍然考虑枚举一下上边界$i$。对于每一个下边界$j$,记$len_{i,j}$表示以$i$为上边界,以$j$为下边界的矩形左右边界的长度。线段树的第$j$个位置,存的是$len_{i,j}-y_j$。那么对于每个上边界,我们只需在线段树上查询一下最大值,再加上$y_i$并乘上$2$,就是以$i$为上边界的矩形的最大周长。接下来考虑如何更新线段树上的答案。

考虑用左右两个单调栈,分别维护一下最靠近中线的点的位置。左边的单调栈内的元素,$x$坐标递增,$y$坐标递减;右边的单调栈内的元素,$x$坐标递减,$y$坐标递减。每次往单调栈中新加入一个点$i$,就按照$y$坐标来选择加入哪一个单调栈。单调栈弹栈的时候,一次一次在线段树上对应的区间修改。每次弹栈会把弹掉的点到这个新加的点这一段内,左边界到中线的距离更新,直接在线段树上修改即可。因为线段树是维护的$len_{i,j}-y_j$,所以线段树的每次修改,就是修改新的上边界条件下,每个点为下边界的$len_{i,j}$,直接区间减去弹掉的点与新加的点的$x$坐标差即可。注意如果加入的点没有导致弹栈的话,那么$i$这个点为下边界的可行区间的左右端点就应该是$0$与$h$。

实现上很多细节一定要看看代码。时间复杂度$O(n\log n)$。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int N=2e5+10;
struct node{
int x,y;
bool operator < (const node &rhs) const {
return x<rhs.x;
}
}a[N],stl[N],str[N];
int w,h,n,ans;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct Seg_T{
#define mid ((l+r)>>1)
int Max[N<<2],Tag[N<<2];
inline void Push_Down(int o){
if(Tag[o]){
Max[o<<1]+=Tag[o],Max[o<<1|1]+=Tag[o];
Tag[o<<1]+=Tag[o],Tag[o<<1|1]+=Tag[o];
Tag[o]=0;
}
}
void Modify(int o,int l,int r,int L,int R,int val){
if(L<=l && r<=R){
Max[o]+=val;Tag[o]+=val;
return;
}
Push_Down(o);
if(L<=mid)Modify(o<<1,l,mid,L,R,val);
if(R>mid)Modify(o<<1|1,mid+1,r,L,R,val);
Max[o]=max(Max[o<<1],Max[o<<1|1]);
}
}T;
inline void Calc(){
memset(T.Max,0,sizeof(T.Max)),memset(T.Tag,0,sizeof(T.Tag));
sort(a+1,a+n+1);
int i,tpl,tpr;tpl=tpr=0;
for(i=1;i<=n-1;i++){
int nex=i-1;
if(a[i].y<=h/2){
while(tpl && stl[tpl].y<a[i].y){
T.Modify(1,1,n,stl[tpl].x,nex,stl[tpl].y-a[i].y);
nex=stl[tpl].x-1,tpl--;
}
if(nex!=i-1)stl[++tpl]=(node){nex+1,a[i].y};
}
else{
while(tpr && str[tpr].y>a[i].y){
T.Modify(1,1,n,str[tpr].x,nex,a[i].y-str[tpr].y);
nex=str[tpr].x-1,tpr--;
}
if(nex!=i-1)str[++tpr]=(node){nex+1,a[i].y};
}
stl[++tpl]=(node){i,0};
str[++tpr]=(node){i,h};
T.Modify(1,1,n,i,i,h-a[i].x);
ans=max(ans,T.Max[1]+a[i+1].x);
}
}
int main(){
int i,j,k,m;
#ifndef ONLINE_JUDGE
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
#endif
w=read();h=read();n=read();
for(i=1;i<=n;i++){
int x=read(),y=read();
a[i]=(node){x,y};
}
a[++n]=(node){0,0},a[++n]=(node){w,h};
Calc();
for(i=1;i<=n;i++)swap(a[i].x,a[i].y);swap(w,h);
Calc();
printf("%d\n",ans<<1);
return 0;
}