专栏文章

题解：P9514 [JOI Open 2023] 花园 / Garden

MMeta_Morph
P9514题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6qqqa
此快照首次捕获于
2025/12/01 21:28
3 个月前
此快照最后确认于
2025/12/01 21:28
3 个月前
查看原文

[JOI Open 2023] 花园 / Garden 题解

博客园链接：[JOI Open 2023] 花园 / Garden 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

单调队列。

分析

首先可以看出所有的坐标范围都只需要在 [0,2D)[0,2D) 取到即可。
这类求矩形面积相关的题目有一个套路：枚举左下角，那么它的两维范围是 [0,D)[0,D)。
A 类比较简单，它的存在只是让我们固定了最小范围，比如一个 (P,Q)(P,Q)，假设现在有一个点 (x,y)(x,y)，如果它作为矩形左下角，那么右上角 (x′,y′)(x',y') 需要满足：
  1. xx 轴：
    • x≤Px\le P，x′≥Px'\ge P。
    • x>Px > P，x′≥P+Dx'\ge P+D。
  2. yy 轴：
    • y≤Qy\le Q，y′≥Qy'\ge Q。
    • y>Qy > Q，y′≥Q+Dy'\ge Q+D。
所以 A 类可以开两个 O(D)O(D) 的数组 AXx,AYyAX_x,AY_y 用前缀最值预处理出来。
B 类其实也一样，对于一个 (R,S)(R,S)，假设现在有一个点 (x,y)(x,y)，如果它作为矩形左下角，那么右上角 (x′,y′)(x',y') 需要满足以下两个条件的其中一个：
  1. xx 轴：
    • x≤Rx\le R，x′≥Rx'\ge R。
    • x>Rx > R，x′≥R+Dx'\ge R+D。
  2. yy 轴：
    • y≤Sy\le S，y′≥Sy'\ge S。
    • y>Sy > S，y′≥S+Dy'\ge S+D。
现在枚举左下角 (x,y)(x,y)。
考虑单调队列做法，枚举每个 xx 值，O(M)O(M) 处理出每个 yy 对应的最小 xx 值 BXyBX_y：对于一个 (R,S)(R,S)，我们将其 SS 记在 R−1,R+D−1R-1,R+D-1 两个值上，枚举 yy 时，我们将它滑动窗口的范围设为 [y,y+D−1)[y,y+D-1)，然后枚举单调队列中的值即可。
那么我们得到了一个 O(D3+DM)O(D^3+DM) 的算法。
发现每次 O(M)O(M) 预处理出的数组有很多重复部分，可以离线，每个 (R,S)(R,S) 只需在 0,R+10,R+1 两个 xx 轴坐标分别做两次修改。
然后单调队列中的值只需要在 yy 删除的时候与 y−1y-1 做一次更新即可，容易看出这样是最优的，O(D3)O(D^3) 变为 O(D2)O(D^2)。
注意有一些边界条件要特殊处理。
总复杂度 O(N+M+D2)O(N+M+D^2)。

代码

CPP
constexpr int N(5e5+10),_D(5e3+10);

int n,m,D,ans;
int AX[_D],AY[_D],BX[_D<<1];
vector<int> vec[_D];

int cal(int xa,int xb,int ya,int yb) { return (xb-xa+1)*(yb-ya+1); }

signed main() {
#ifdef plus_cat
	freopen(plus_cat ".in","r",stdin),freopen(plus_cat ".out","w",stdout);
#endif // plus_cat
	/*DE("Input");*/
	scanf("%d%d%d",&n,&m,&D),ans=D*D;
	/*DE("Solve A class");*/
	FOR(i,1,n) {
		int x,y;
		scanf("%d%d",&x,&y);
		tomax(AX[0],x),tomax(AX[x+1],x+D);
		tomax(AY[0],y),tomax(AY[y+1],y+D);
	}
	FOR(i,1,D)tomax(AX[i],i,AX[i-1]),tomax(AY[i],i,AY[i-1]);
	/*DE("Record B class");*/
	FOR(y,0,2*D-1)BX[y]=0;
	FOR(i,1,m) {
		int x,y;
		scanf("%d%d",&x,&y);
		if(y>0)tomax(BX[y-1],x);
		tomax(BX[y+D-1],x),vec[x+1].push_back(y);
	}
	/*DE("Solve");*/
	FOR(x,0,D-1) {
		tomin(ans,cal(x,AX[x],0,D-1));
		for(int y:vec[x]) {
			if(y>0)tomax(BX[y-1],x+D-1);
			tomax(BX[y+D-1],x+D-1);
		}
		int it(0),h(1),t(0);
		static int q[_D<<1];
		auto update=[&](int i,int y) {
			if(y<0)return;
			int _y(max(q[i-1]+1,AY[y]));
			tomin(ans,cal(x,max(AX[x],BX[q[i]]),y,_y));
		};
		FOR(y,0,D-1) {
			while(it<y+D-1) {
				while(h<=t&&BX[it]>BX[q[t]])update(t--,y-1);
				q[++t]=it++;
			}
			while(h<=t&&q[h]<AY[y])update(h++,y-1);
		}
		while(h<=t)update(h++,D-1);
	}
	/*DE("Output");*/
	printf("%d\n",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...