20200730 T3 small B farm [maximum perimeter empty rectangle (monotone stack + line segment tree)] & "ROI 2017 day 2" learning track

Small B The farm

Title Description

$n\le 3\ast 10^5$

Topic analysis

$n^2\log n$ To enumerate the left boundary , The right boundary enumerates from large to small , Maintain midpoint $y$ The maximum value of the difference between two adjacent points of an axis , When deleting a point, add the difference between its upper and lower adjacent two points , Two way linked list .

$n\log n$ practice ：
Because it's the whole hour , The answer is at least $2\ast (\max (W,H)+1)$, So the answer rectangle must go through $x=\frac{W}{2}$ or $y=\frac{H}{2}$ One of the straight lines .（ Otherwise, it can only be framed in a quarter of the area ）

Assume that after $x=\frac{W}{2}$ This line , Press $y$ Sort from small to large , Enumerate the upper boundary of the rectangle , Maintain the widest width corresponding to the lower boundary of each rectangle , The lower it goes, the narrower it becomes , You can use monotone stack + Segment tree interval plus maintenance .

Implementation , You need a monotone stack on the left and right , Each point on the left will draw a left boundary for the lower boundary below it （ Not including myself ）, The initial value of the segment tree is the value of each point $-y$, Add the additional width and take max, And the current upper boundary $y$ Adding together is the answer .
$y$ Equal points do not require special treatment , And the following answers will be counted at the first point , Click the normal box for other items .

Code：

#include<bits/stdc++.h>
#define maxn 300005
using namespace std;
int n,W,H,ans;
struct node{
    
	int x,y;
	bool operator < (const node &p)const{
    return y<p.y;}
}a[maxn];
#define lc i<<1
#define rc i<<1|1
int mx[maxn<<2],tag[maxn<<2];
void build(int i,int l,int r){
    
	tag[i]=0;
	if(l==r) return void(mx[i]=W-a[l].y);
	int mid=(l+r)>>1;
	build(lc,l,mid),build(rc,mid+1,r);
	mx[i]=max(mx[lc],mx[rc]);
}
void ins(int i,int l,int r,int x,int y,int v){
    
	if(x>r||y<l) return;
	if(x<=l&&r<=y) {
    mx[i]+=v,tag[i]+=v;return;}
	int mid=(l+r)>>1;
	ins(lc,l,mid,x,y,v),ins(rc,mid+1,r,x,y,v);
	mx[i]=max(mx[lc],mx[rc])+tag[i];
}
int A[maxn],An,B[maxn],Bn;
void solve(){
    
	sort(a+1,a+1+n);
	build(1,0,n-1),An=Bn=0;
	for(int i=1;i<=n;i++){
    
		ans=max(ans,a[i].y+mx[1]);
		if(a[i].x<=W/2){
    
			ins(1,0,n-1,A[An],i-1,-a[i].x);
			while(An&&a[A[An]].x<a[i].x) ins(1,0,n-1,A[An-1],A[An]-1,-a[i].x+a[A[An]].x),An--;
			A[++An]=i;
		}
		else{
    
			ins(1,0,n-1,B[Bn],i-1,a[i].x-W);
			while(Bn&&a[B[Bn]].x>a[i].x) ins(1,0,n-1,B[Bn-1],B[Bn]-1,a[i].x-a[B[Bn]].x),Bn--;
			B[++Bn]=i;
		}
	}
}
int main()
{
    
	//freopen("farm.in","r",stdin);
	//freopen("farm.out","w",stdout);
	scanf("%d%d%d",&W,&H,&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	a[++n]=(node){
    W,H};
	solve();
	for(int i=1;i<=n;i++) swap(a[i].x,a[i].y);
	swap(W,H),solve();
	printf("%d\n",ans*2);
}

---

LOJ#2773. 「ROI 2017 Day 2」 Learning track

Code：

#include<bits/stdc++.h>
#define maxn 500005
#define LL long long
using namespace std;
char cb[1<<20],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &a){
    
	char c;while(!isdigit(c=getc()));
	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0');
}
int n,m,a[maxn],b[maxn],c[maxn*2],p[maxn],pn,al,ar,bl,br,pos[maxn],A[maxn],An,B[maxn],Bn;//A[0],B[0] are used as 0!
LL ans,x[maxn],y[maxn];
LL mx[maxn<<2],tag[maxn<<2];
void build(int i,int l,int r,LL x,LL *y){
    
	tag[i]=0;
	if(l==r) return void(mx[i]=x-y[p[l]]);
	int mid=(l+r)>>1;
	build(i<<1,l,mid,x,y),build(i<<1|1,mid+1,r,x,y);
	mx[i]=max(mx[i<<1],mx[i<<1|1]);
}
void mdf(int i,int l,int r,int x,int y,LL v){
    
	if(x<=l&&r<=y) {
    mx[i]+=v,tag[i]+=v;return;}
	int mid=(l+r)>>1;
	if(x<=mid) mdf(i<<1,l,mid,x,y,v);
	if(y>mid) mdf(i<<1|1,mid+1,r,x,y,v);
	mx[i]=max(mx[i<<1],mx[i<<1|1])+tag[i];
}
int find(int i,int l,int r){
    
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(mx[i]==mx[i<<1]+tag[i]) return find(i<<1,l,mid);
	else return find(i<<1|1,mid+1,r);
}
inline void updans(LL x,int a,int b,int c,int d,bool flg){
    
	if(flg) swap(a,c),swap(b,d);
	if(x>ans) ans=x,al=a,ar=b,bl=c,br=d;
}
void solve(int n,int m,int *a,int *b,LL *x,LL *y,bool flg){
    
	int mid=lower_bound(x+1,x+1+n,x[n]>>1)-x; pn=0;
	for(int i=1;i<=m;i++) if(b[i]) p[++pn]=i,pos[pn]=b[i]; p[pn+1]=m+1;
	build(1,0,pn,x[n],y);
	for(int i=An=Bn=0;i<=pn;i++){
    
		if(i){
    
			if(pos[i]<=mid){
    
				mdf(1,0,pn,A[An],i-1,-x[pos[i]]);
				while(An&&pos[i]>pos[A[An]]) mdf(1,0,pn,A[An-1],A[An]-1,-x[pos[i]]+x[pos[A[An]]]),--An;
				A[++An]=i;
			}
			else{
    
				mdf(1,0,pn,B[Bn],i-1,-x[n]+x[pos[i]-1]);
				while(Bn&&pos[i]<pos[B[Bn]]) mdf(1,0,pn,B[Bn-1],B[Bn]-1,-x[pos[B[Bn]]-1]+x[pos[i]-1]),--Bn;
				B[++Bn]=i;
			}
		}
		if(y[p[i+1]-1]+mx[1]>ans){
    
			int k=find(1,0,pn);
			int l=upper_bound(A+1,A+1+An,k)-A; l = l<=An?b[p[A[l]]]+1:1;
			int r=upper_bound(B+1,B+1+Bn,k)-B; r = r<=Bn?b[p[B[r]]]-1:n;
			updans(y[p[i+1]-1]+mx[1],l,r,p[k]+1,p[i+1]-1,flg);
		}
	}
}
int main()
{
    
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(x[i]),x[i]+=x[i-1];
	for(int i=1;i<=m;i++) read(b[i]);
	for(int i=1;i<=m;i++) read(y[i]),y[i]+=y[i-1];
	updans(x[n],1,n,0,0,0),updans(y[m],0,0,1,m,0);
	for(int i=1;i<=m;i++) c[b[i]]=i,b[i]=0;
	for(int i=1;i<=n;i++) a[i]=c[a[i]],b[a[i]]=i;
	solve(n,m,a,b,x,y,0),solve(m,n,b,a,y,x,1);
	printf("%lld\n%d %d\n%d %d\n",ans,al,ar,bl,br);
}