[DS记录]AT2149 [ARC063D] すぬけ君の塗り絵 2 / Snuke's Coloring 2
command_block
2021-05-13 09:07:57
**题意** ： 平面上有一个左下角坐标 $(0,0)$ 右上角坐标 $(W,H)$ 的矩形，起初长方形内部被涂白。
现在给定 $n$ 个点，你每次在以下 $4$ 种操作中选择一种：
- 将矩形内 $x>x_i$ 的区域涂黑
- 将矩形内 $x<x_i$ 的区域涂黑
- 将矩形内 $y<y_i$ 的区域涂黑
- 将矩形内 $y>y_i$ 的区域涂黑
不难发现，最后剩下的白色部分是一个矩形，最大化该矩形的周长。
$n\leq 3\times 10^5$ ，时限$\texttt{4s}$。
------------
题意不难转化为 ： 求一个周长最大的矩形，使得内部没有特殊点。
考虑分治，每次处理经过 $y=m$ 的矩形。
对于某个给定的 $x$ 的区间，矩形的高是容易确定的，只需要得到两侧距离的 $\min$ 即可。
进一步对 $x$ 进行分治，当处理跨越 $x=c$ 的贡献时，根据单调性不难做到线性。
（具体地，需要双指针和单调队列）
两个分治嵌套，复杂度为 $O(n\log^2n)$。
不难发现， $1\times H,\ W\times 1$ 的矩形总是能够被选出的。
于是，作为最优答案的矩形必然经过 $y=H/2$ 或者 $x=W/2$ ，否则周长比不过上面两个。
这样，两次分治即可做到 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 300500
using namespace std;
int l1,l2,x[MaxN],y1[MaxN],y2[MaxN],sy1[MaxN],sy2[MaxN]
,o1[MaxN],o2[MaxN],o3[MaxN],ans;
struct MQueue{
int q[MaxN],ql,qr,*x;
void Init(int *tx){x=tx;ql=1;qr=0;}
void push(int i){
while(ql<=qr&&x[q[qr]]<x[i])qr--;
q[++qr]=i;
}
int qry(int lim){
while(ql<=qr&&q[ql]<=lim)ql++;
return ql<=qr ? x[q[ql]] : 0;
}
}Q1,Q2;
void solve(int l,int r)
{
if (l==r){
ans=max(ans,y1[l]+y2[l]+x[l+1]-x[l-1]);
return ;
}int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
sy1[mid]=l2/2;sy2[mid]=(l2+1)/2;
for (int i=mid+1;i<=r;i++){
sy1[i]=min(sy1[i-1],y1[i]);
sy2[i]=min(sy2[i-1],y2[i]);
}
o3[r+1]=0;
for (int i=r;i>mid;i--){
o1[i]=sy1[i]+x[i+1];o2[i]=sy2[i]+x[i+1];
o3[i]=max(o3[i+1],x[i+1]+sy1[i]+sy2[i]);
}
Q1.Init(o1);Q2.Init(o2);
for (int i=mid,ty1=l2/2,ty2=(l2+1)/2,p1=mid,p2=mid;i>=l;i--){
ty1=min(ty1,y1[i]);ty2=min(ty2,y2[i]);
while(p1<r&&y1[p1+1]>=ty1)Q2.push(++p1);
while(p2<r&&y2[p2+1]>=ty2)Q1.push(++p2);
ans=max(ans,x[min(p1,p2)+1]-x[i-1]+ty1+ty2);
ans=max(ans,o3[max(p1,p2)+1]-x[i-1]);
ans=max(ans,Q1.qry(p1)+ty2-x[i-1]);
ans=max(ans,Q2.qry(p2)+ty1-x[i-1]);
}
}
struct Point{int x,y;}p[MaxN];
bool cmp(const Point &A,const Point &B)
{return A.x<B.x;}
int tn,n;
void calc()
{
sort(p+1,p+n+1,cmp);
tn=0;
for (int i=1;i<=n;i++){
int ty=p[i].y-l2/2;
if (i>1&&p[i].x==p[i-1].x){
if (ty<0)y1[tn]=min(y1[tn],-ty);
else y2[tn]=min(y2[tn],ty);
}else {
x[++tn]=p[i].x;
if (ty<0){y1[tn]=-ty;y2[tn]=(l2+1)/2;}
else {y1[tn]=l2/2;y2[tn]=ty;}
}
}x[tn+1]=l1;
for (int i=1;i<=tn;i++)
ans=max(ans,l2+x[i+1]-x[i]);
solve(1,tn);
}
int main()
{
scanf("%d%d%d",&l1,&l2,&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
calc();
for (int i=1;i<=n;i++)
swap(p[i].x,p[i].y);
swap(l1,l2);calc();
printf("%d",ans*2);
return 0;
}
```