题面
给一个 (W imes H) 的矩形和 (n) 个点 ((x_i,y_i))。对于每个点，都必须把它四个方向之一的区域全涂黑。最后留下一个白色矩形，求它的周长最大值。
数据范围：(1le W,Hle 10^8)，(1le Nle 3 imes 10^5)。
题解
题目就是要求一个周长最大的矩形，在给定矩形内，且不包含给定的点。
答案至少是 (2max(W,H))，把矩形选成长条形的即可。
所以 (x,y) 中至少有一维，答案矩形越过给定矩形中线。
假设越过 (y) 轴中线（否则同理）。
对给定的点按 (x) 轴排序。枚举矩形的右端点在第几个点，设为 (i+1)。
如果当前的点 (i) 满足 (y_i<frac H2)，那么这个点可以看成限制区间 ([y_i,H])。
否则可以看成限制区间 ([0,y_i])。
用一棵线段树维护当左端点在第 (j) 个点时的 (ans-x_{i+1}) 最大值。
线段树支持区间加减和全局最大值。
所以可以维护两个年轻栈，一个在 (frac H2) 下端，一个在 (frac H2) 上端。
栈中的元素是之前的点，用二元组 ((j,y)) 表示。
表示从 (j) 到 (i+1) 矩阵的上边最大/下边最小为 (y)。
假设 (y_i<frac H2)（否则同理），就用 (y_i) 把下端栈的栈顶 (<y_i) 的 pop 掉。
每 pop 一次，象征着左端点在被 pop 掉的区域的下边被抬升了，在线段树上修改。
在最后被 pop 的地方 (r) 之右，这些地方作为左端点的下边都是 (y_i)。
所以往下端栈中加入元素 ((r,y_i))。
假设第 (i) 个点和 (i+1) 个点中有个虚拟点在最顶上/底下。
所以在 (i) 这个地方的线段树上单点修改 (+H)。
还要 (-x_i)，为了到时候可以计算横向区间长度。
同时在上端栈加入 ((i,H))，下端加入 ((i,0))。
然后统计右端点在 (i+1) 点的贡献：线段树全局最大值 (+x_{i+1})。
最后要输出求出来的答案 ( imes 2)。
时间复杂度 (Theta(nlog n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=3e5+4;
int n,W,H,ns;
stack<pair<int,int>> us,ds;
pair<int,int> a[N];
//SegmentTree
const int sN=N<<2;
#define mid ((l+r)>>1)
int mx[sN],tag[sN];
void pushup(int u){mx[u]=max(mx[u*2+1],mx[u*2+2]);}
void down(int u,int v){mx[u]+=v,tag[u]+=v;}
void pushdown(int u){if(tag[u]) down(u*2+1,
tag[u]),down(u*2+2,tag[u]),tag[u]=0;}
void add(int x,int y,int v,int u=0,int l=0,int r=n){
// if(u==0) cout<<x<<' '<<y<<' '<<v<<'
';
if(y<=l||r<=x) return;
if(x<=l&&r<=y) return down(u,v);
pushdown(u),add(x,y,v,u*2+1,l,mid),
add(x,y,v,u*2+2,mid,r),pushup(u);
}
#undef mid
//Function
void solve(){
// cout<<"solving
";
sort(a,a+n);
R(i,n-1){
if(a[i].y<(H>>1)){
int r=i;
while(sz(ds)&&ds.top().y<a[i].y){
const int l=ds.top().x;
add(l,r,ds.top().y-a[i].y),r=l,ds.pop();
}
ds.push(mp(r,a[i].y));
} else {
int r=i;
while(sz(us)&&us.top().y>a[i].y){
const int l=us.top().x;
add(l,r,a[i].y-us.top().y),r=l,us.pop();
}
us.push(mp(r,a[i].y));
}
us.push(mp(i,H)),ds.push(mp(i,0));
add(i,i+1,H-a[i].x),ns=max(ns,mx[0]+a[i+1].x);
}
while(sz(ds)) ds.pop();
while(sz(us)) us.pop();
R(u,n<<2) mx[u]=tag[u]=0;
}
//Main
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>W>>H>>n; //,ns=max(W,H);
R(i,n) cin>>a[i].x>>a[i].y;
a[n++]=mp(0,0),a[n++]=mp(W,H);
solve(),swap(W,H);
R(i,n) swap(a[i].x,a[i].y);
solve(),cout<<(ns<<1)<<'
';
return 0;
}
祝大家学习愉快！