自动搬运

查看原文

来自洛谷，原作者为

	Kubic Go straight ahead 'til we've lost it all.

搬运于2025-08-24 22:43:46，当前版本为作者最后更新于2022-12-31 20:27:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

称一个好区域是极大的当且仅当它的边界上至少有 $3$ 个点。有结论：一定存在一组最优解，使得它是一个极大好区域。不妨设是左，右，下边界上有点。

枚举下边界上的点，有结论：最多只有一个合法的极大好区域。

也就是说，可能成为答案的极大好区域只有 $O(n)$ 个。

考虑怎么找到一个点 $(x,y)$ 对应的极大好区域。

我们可以考虑钦定这个区域的边长 $l$，分别找到左右两边第一个纵坐标在 $(y,y+l)$ 内的点，设为 $(x_1,y_1),(x_2,y_2)$。

二分出最大的 $l$ 满足 $x_2-x_1\ge l$。如果 $x_2-x_1=l$ 则我们已经求出了极大好区域，否则要么不存在极大好区域，要么存在一个纵坐标为 $y+l$ 的点在极大好区域的角上，找到这个点即可求出极大好区域。可以在主席树上二分，时间复杂度 $O(n\log n)$。

这里有一个减小常数的方法：没有必要对四个方向各做一遍，只需要做 左右上 和 左右下 这两种情况即可，可以证明这样不会漏掉任何极大好区域。

求出这 $O(n)$ 个极大好区域之后，可以考虑用扫描线 + 线段树求出答案。一般的做法是对于每个节点维护一个 set，其中包含当前覆盖这个节点的所有正方形。这样做的时间复杂度是 $O(n\log^2 n)$。

但实际上我们可以利用正方形的性质进行优化。对于每个节点，如果其中有两个正方形 $S_1,S_2$ 满足 $|S_1|>|S_2|$ 且 $S_1$ 的右边界在 $S_2$ 的右边界的右侧，那么显然 $S_2$ 就没用了。

因此我们可以对于每个节点维护一个 deque，里面包含当前覆盖这个节点并且有用的正方形。这个 deque 中的所有正方形满足边长单调递减，且右边界的位置单调递增。加入一个新的正方形时边长比它小的正方形显然都没用了，直接从末尾弹出即可，然后再判断它本身是否有用即可。时间复杂度均摊 $O(n\log n)$。

因此总时间复杂度为 $O(n\log n)$，常数很大。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 300005
#define LIM 10000005
#define mid ((l+r)/2)
#define pb push_back
#define po pop_back
#define gc() (P1==P2 && (P2=(P1=buf)+fread(buf,1,LIM,stdin),P1==P2)?EOF:*P1++)
const int INF1=1e8,INF2=3e8,INF3=5e8;char buf[LIM],*P1=buf,*P2=buf;
int n,m,dsX[N],dsY[N],X[N],Y[N],o[N],ans[N];struct Node {int x,w;};
int tp;struct Sqr {int x,y,w;}z[N*4];vector<Sqr> vc[N];
int cntS,rt1[N],rt2[N];struct Seg {int vl,ch[2];}sg[N*40];
struct Seg1 {int hd;vector<Node> vc;}sg1[N*4];
bool cmp(Sqr x,Sqr y) {return x.x<y.x;}
int rd()
{
	int res=0;char c=0;while(!isdigit(c)) c=gc();
	while(isdigit(c)) res=res*10+(c-48),c=gc();return res;
}
void upd(int p,int &p1,int l,int r,int x,int vl)
{
	sg[p1=++cntS]=sg[p];sg[p1].vl=vl;if(l==r) return;
	if(x<=mid) upd(sg[p].ch[0],sg[p1].ch[0],l,mid,x,vl);
	else upd(sg[p].ch[1],sg[p1].ch[1],mid+1,r,x,vl);
}
int qry1(int p1,int p2,int l,int r,int x,int &vl1,int &vl2)
{
	if(l>=x)
	{
		int t,t1=min(vl1,sg[p1].vl),t2=min(vl2,sg[p2].vl);
		if(dsY[r]-dsY[x]<t1+t2) {vl1=t1;vl2=t2;return -1;}if(l==r) return l;
		t=qry1(sg[p1].ch[0],sg[p2].ch[0],l,mid,x,vl1,vl2);if(~t) return t;
		return qry1(sg[p1].ch[1],sg[p2].ch[1],mid+1,r,x,vl1,vl2);
	}int t=-1;if(x<=mid) t=qry1(sg[p1].ch[0],sg[p2].ch[0],l,mid,x,vl1,vl2);
	if(~t) return t;return qry1(sg[p1].ch[1],sg[p2].ch[1],mid+1,r,x,vl1,vl2); 
}
int qry2(int p1,int p2,int l,int r,int x,int &vl1,int &vl2)
{
	if(r<=x)
	{
		int t,t1=min(vl1,sg[p1].vl),t2=min(vl2,sg[p2].vl);
		if(dsY[x]-dsY[l]<t1+t2) {vl1=t1;vl2=t2;return -1;}if(l==r) return l;
		t=qry2(sg[p1].ch[1],sg[p2].ch[1],mid+1,r,x,vl1,vl2);if(~t) return t;
		return qry2(sg[p1].ch[0],sg[p2].ch[0],l,mid,x,vl1,vl2);
	}int t=-1;if(x>mid) t=qry2(sg[p1].ch[1],sg[p2].ch[1],mid+1,r,x,vl1,vl2); 
	if(~t) return t;return qry2(sg[p1].ch[0],sg[p2].ch[0],l,mid,x,vl1,vl2); 
}
void upd1(int p,int l,int r,int qL,int qR,Node vl)
{
	if(qL>qR) return;
	if(l>=qL && r<=qR)
	{
		while(sg1[p].vc.size()>sg1[p].hd && vl.w>=(--sg1[p].vc.end())->w)
			sg1[p].vc.po();
		if(sg1[p].vc.size()<=sg1[p].hd || vl.x>(--sg1[p].vc.end())->x)
			sg1[p].vc.pb(vl);return;
	}if(qL<=mid) upd1(p*2,l,mid,qL,qR,vl);if(qR>mid) upd1(p*2+1,mid+1,r,qL,qR,vl);
}
int qry(int p,int l,int r,int x,int o)
{
	while(sg1[p].vc.size()>sg1[p].hd && sg1[p].vc[sg1[p].hd].x<o) ++sg1[p].hd;
	int t=0;if(sg1[p].vc.size()>sg1[p].hd) t=sg1[p].vc[sg1[p].hd].w;
	if(l==r) return t;if(x<=mid) return max(t,qry(p*2,l,mid,x,o));
	return max(t,qry(p*2+1,mid+1,r,x,o));
}
int main()
{
	n=rd();m=rd();sg[0].vl=INF2;dsX[0]=dsY[0]=-INF3;
	for(int i=1;i<=n;++i) X[i]=rd(),Y[i]=rd(),dsX[i]=X[i],dsY[i]=Y[i];
	dsX[n+1]=dsY[n+1]=INF3;sort(dsX+1,dsX+n+1);sort(dsY+1,dsY+n+1);
	for(int i=1;i<=n;++i)
	{
		X[i]=lower_bound(dsX+1,dsX+n+1,X[i])-dsX;
		Y[i]=lower_bound(dsY+1,dsY+n+1,Y[i])-dsY;	
	}for(int i=1;i<=n;++i) o[X[i]]=Y[i];
	upd(rt1[0],rt1[0],0,n+1,0,-INF2);upd(rt2[n+1],rt2[n+1],0,n+1,0,-INF2);
	upd(rt1[0],rt1[0],0,n+1,n+1,-INF2);upd(rt2[n+1],rt2[n+1],0,n+1,n+1,-INF2);
	for(int i=1;i<=n;++i) upd(rt1[i-1],rt1[i],0,n+1,o[i],-dsX[i]);
	for(int i=n;i;--i) upd(rt2[i+1],rt2[i],0,n+1,o[i],dsX[i]);
	for(int i=1,vl1,vl2,t;i<=n;++i)
	{
		vl1=vl2=INF2;t=qry1(rt1[i-1],rt2[i+1],0,n+1,o[i],vl1,vl2);
		if(dsY[t]-dsY[o[i]]<vl1+vl2)
		{
			t=dsY[t]-dsY[o[i]];z[++tp]=(Sqr) {-vl1,dsY[o[i]],t};
			z[++tp]=(Sqr) {vl2-t,dsY[o[i]],t};
		}else z[++tp]=(Sqr) {-vl1,dsY[o[i]],vl1+vl2};
		vl1=vl2=INF2;t=qry2(rt1[i-1],rt2[i+1],0,n+1,o[i],vl1,vl2);
		if(dsY[o[i]]-dsY[t]<vl1+vl2)
		{
			t=dsY[o[i]]-dsY[t];z[++tp]=(Sqr) {-vl1,dsY[o[i]]-t,t};
			z[++tp]=(Sqr) {vl2-t,dsY[o[i]]-t,t};
		}else z[++tp]=(Sqr) {-vl1,dsY[o[i]]-vl1-vl2,vl1+vl2};
	}z[++tp]=(Sqr) {dsX[1]-INF2,-1,INF2};z[++tp]=(Sqr) {dsX[n],-1,INF2};
	for(int i=1;i<=m;++i) X[i]=rd(),Y[i]=rd(),dsX[i]=X[i],dsY[i]=Y[i];
	sort(dsX+1,dsX+m+1);sort(dsY+1,dsY+m+1);
	for(int i=1;i<=m;++i)
	{
		X[i]=lower_bound(dsX+1,dsX+m+1,X[i])-dsX;
		Y[i]=lower_bound(dsY+1,dsY+m+1,Y[i])-dsY;	
	}for(int i=1;i<=m;++i) o[X[i]]=Y[i];
	for(int i=1,x;i<=tp;++i)
		x=upper_bound(dsX+1,dsX+m+1,z[i].x)-dsX,vc[x].pb(z[i]);
	for(int i=1,l,r;i<=m;++i)
	{
		sort(vc[i].begin(),vc[i].end(),cmp);
		for(auto j:vc[i])
		{
			l=upper_bound(dsY+1,dsY+m+1,j.y)-dsY;
			r=lower_bound(dsY+1,dsY+m+1,j.y+j.w)-dsY-1;
			upd1(1,1,m,l,r,(Node) {j.x+j.w-1,j.w});
		}ans[i]=qry(1,1,m,o[i],dsX[i]);if(ans[i]>INF1) ans[i]=-1;
	}for(int i=1;i<=m;++i) printf("%d\n",ans[X[i]]);return 0;
}