Electro Master

Electro Master

上午唯一写出的题。

题意

给定 $n$ 个矩形，值域范围 $r\times c$，求有被至少 $n-1$ 个矩形覆盖的位置数目。

Sol

考场做法：

首先考虑如何计算被 $n$ 个矩形全部覆盖的位置数目。我们对于所有的矩形 $(x_0,y_0,x_1,y_1)$，统计 $\max\{x_0\},\max\{y_0\},\min\{x_1\},\min\{y_1\}$，那么所得到的坐标满足 $x_0\leq x_1,y_0 \leq y_1$ 即所有矩形的交集。

现在考虑统计被 $n-1$ 个矩形全部覆盖的位置数目。我们可以在所有的 $n$ 个矩形中枚举删除哪一个矩形，那么当删除的矩形与我们所求的到矩形交集无关，那么贡献依旧是矩形的交集；否则，相应地，我们求出所有关于 $x_0,y_0,x_1,y_1$ 的次小值，那么可以方便的得到贡献。

注意开 long long，还有就是需要容斥计算贡献。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e6+1e1;
const lint INF=1e18+1e9;

struct Matrix{
	int x0,y0,x1,y1;
}M[MAXN];
int Upl,Maxl,Minr,Dnr,UpL,MaxL,MinR,DnR,n,r,c,
	cntx0,cnty0,cntx1,cnty1,px0,py0,px1,py1;
lint Ans,tmp;

void Area(int x0,int y0,int x1,int y1){
	if(x0<=x1 && y0<=y1) Ans+=1ll*(x1-x0+1)*(y1-y0+1);
	return;
}

int main(void){
	
	Dnr=DnR=Minr=MinR=inf;
	scanf("%d%d%d",&n,&r,&c);
	for(int i=1;i<=n;i++){
		M[i].x0=readint,M[i].y0=readint,
		M[i].x1=readint,M[i].y1=readint;
	}
	for(int i=1;i<=n;i++){//max,min
		if(Upl<M[i].y0) Upl=M[i].y0,py0=i;
		if(Dnr>M[i].y1) Dnr=M[i].y1,py1=i;
		if(Maxl<M[i].x0) Maxl=M[i].x0,px0=i;
		if(Minr>M[i].x1) Minr=M[i].x1,px1=i;
	}
	Area(Maxl,Upl,Minr,Dnr),tmp=Ans;
	for(int i=1;i<=n;i++){//second max,min
		if(cnty0 || Upl!=M[i].y0) UpL=max(M[i].y0,UpL);
		else ++cnty0;
		if(cnty1 || Dnr!=M[i].y1) DnR=min(M[i].y1,DnR);
		else ++cnty1;
		if(cntx0 || Maxl!=M[i].x0) MaxL=max(M[i].x0,MaxL);
		else ++cntx0;
		if(cntx1 || Minr!=M[i].x1) MinR=min(M[i].x1,MinR);
		else ++cntx1;
	}
	for(int i=1;i<=n;i++){
		int x0=(px0==i ? MaxL : Maxl),y0=(py0==i ? UpL : Upl),
			x1=(px1==i ? MinR : Minr),y1=(py1==i ? DnR : Dnr);
		Area(x0,y0,x1,y1),Ans-=tmp;
	}
	printf("%lld\n",Ans);

	return 0;
}

std 做法：

我们考虑把矩形的交集作为一种运算 $\cap$，算出前缀交 $pre$、后缀交 $nxt$，那么依旧枚举删除第 $i$ 个矩形，再求出 $pre_{i-1}\cap nxt_{i+1}$，统计答案。代码略。