2018.09.22 atcoder Snuke's Coloring 2（線段樹+單調棧）

傳送門

就是給出一個矩形，上面有一些點，讓你找出一個周長最大的矩形，滿足沒有一個點在矩形中。

這個題很有意思。

考慮到答案一定會穿過中線。

于是我們可以把點分到中線兩邊。

先想想暴力如何解決。

顯然就是枚舉矩形的上下邊的坐标然後求兩邊的最大寬度。

用單調棧搞一下這樣的效率是 O ( n 2 ) O(n^2) O(n2)的。

考慮繼續優化。

幹脆我們隻枚舉一條邊，另外一條用線段樹維護最值。

代碼：

#include<bits/stdc++.h>
#define N 300005
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
int w,h,n,top1,top2,ans;
struct Pot{int x,y;}p[N];
struct Node{int l,r,mx,add;}T[N<<2];
struct node{int id,val;}stk1[N],stk2[N];
inline int max(int a,int b){return a>b?a:b;}
inline void pushnow(int p,int v){T[p].mx+=v,T[p].add+=v;}
inline void build(int p,int l,int r){
	T[p].l=l,T[p].r=r,T[p].mx=T[p].add=0;
	if(l==r)return;
	build(lc,l,mid),build(rc,mid+1,r);
}
inline void update(int p,int ql,int qr,int v){
	if(T[p].l>qr||T[p].r<ql)return;
	if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
	if(T[p].add)pushnow(lc,T[p].add),pushnow(rc,T[p].add),T[p].add=0;
	if(qr<=mid)update(lc,ql,qr,v);
	else if(ql>mid)update(rc,ql,qr,v);
	else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
	T[p].mx=max(T[lc].mx,T[rc].mx);
}
inline void swap(int&x,int&y){x^=y,y^=x,x^=y;}
inline bool cmp(Pot a,Pot b){return a.x<b.x;}
inline void solve(){
	sort(p+1,p+n+1,cmp),build(1,1,n),top1=top2=0;
	for(int i=1;i<=n;++i){
		int las=i-1;
		if(p[i].y<=h/2){
			while(top1&&stk1[top1].val<p[i].y){
				update(1,stk1[top1].id,las,stk1[top1].val-p[i].y);
				las=stk1[top1--].id-1;
			}
			if(las!=i-1)stk1[++top1]=(node){las+1,p[i].y};
		}
		else{
			while(top2&&stk2[top2].val>p[i].y){
				update(1,stk2[top2].id,las,p[i].y-stk2[top2].val);
				las=stk2[top2--].id-1;
			}
			if(las!=i-1)stk2[++top2]=(node){las+1,p[i].y};
		}
		stk1[++top1]=(node){i,0},stk2[++top2]=(node){i,h};
		update(1,i,i,h-p[i].x),ans=max(ans,T[1].mx+p[i+1].x);
	}
}
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int main(){
	w=read(),h=read(),n=read();
	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
	p[++n]=(Pot){0,0},p[++n]=(Pot){w,h};
	solve();
	for(int i=1;i<=n;++i)swap(p[i].x,p[i].y);
	swap(w,h);
	solve();
	cout<<ans*2;
	return 0;
}