ABC304D A Piece of Cake

题目大意

平面上有一个蛋糕以及$n$个草莓，这些草莓的坐标分别为$p_1,q_1,p_2,q_2,\dots ,p_n,q_n$。

有下面若干条直线，将蛋糕分为

• 有$A$条平行于$y$轴的直线：$x=a_1,x=a_2,\dots ,x=a_A$
• 有$B$条平行于$x$轴的直线：$y=b_1,y=b_2,\dots ,y=b_B$

这些直线将蛋糕分为$(A+1)(B+1)$份。

小$T$要在这$(A+1)(B+1)$块中选一块。请你告诉他草莓最多的一块和草莓最少的一块。保证没有草莓在块与块的边缘。

$3\le w,h\le 10^9,1\le n\le 2\times 10^5,1\le A,B\le 2\times 10^5$

题解

用$map$来存每块蛋糕的草莓的数量，用一个结构体$t$来存储有草莓的蛋糕的数量，再用$map$来记录每块蛋糕是否加入了$t$中。

$t$的长度不会超过$n$，所以枚举$t$中的蛋糕，找到草莓数量最多的。如果$t$的长度小于$(A+1)(B+1)$，则总有一个蛋糕的草莓数量为$0$，最小值为$0$；否则枚举$t$中的蛋糕，找到草莓数量最少的。

时间复杂度为$O(n\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
int w,h,n,v1,v2,t1=0,m1,m2,x[200005],y[200005],a[200005],b[200005];
map<int,int>wt[200005],z[200005];
struct node{
	int x,y;
}t[1000005];
int main()
{
	scanf("%d%d%d",&w,&h,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
	}
	scanf("%d",&v1);
	for(int i=1;i<=v1;i++){
		scanf("%d",&a[i]);
	}
	a[++v1]=2e9;
	scanf("%d",&v2);
	for(int i=1;i<=v2;i++){
		scanf("%d",&b[i]);
	}
	b[++v2]=2e9;
	for(int i=1;i<=n;i++){
		int d1,d2;
		d1=lower_bound(a+1,a+v1+1,x[i])-a;
		d2=lower_bound(b+1,b+v2+1,y[i])-b;
		++wt[d1][d2];
		if(!z[d1][d2]){
			t[++t1]=(node){d1,d2};
			z[d1][d2]=1;
		}
	}
	m1=2e9;m2=0;
	if(t1<1ll*v1*v2) m1=0;
	for(int i=1;i<=t1;i++){
		int vt=wt[t[i].x][t[i].y];
		m1=min(m1,vt);
		m2=max(m2,vt);
	}
	printf("%d %d",m1,m2);
	return 0;
}