自动搬运

查看原文

来自洛谷，原作者为

	12345678hzx 你说得对，但是Pacman是传奇吃屎王

搬运于2025-08-24 22:48:43，当前版本为作者最后更新于2023-07-31 13:21:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

闲话

这是应该是这几年最简单的题了，连我这个菜鸡都会 $95$ 分做法。

思路

前面 $95$ 分其实就是一个扫描线模板，不懂的可以左转题目。

这题与扫描线模板有些不同，此题给出的是格子的坐标，而扫描线模板给出的是点的坐标，我们在读入时只需将它们的右下角坐标都加 $1$ 即可。

对于斜线，由于最多只有 $5$ 条，且长度不超过 $10^5$，只需将斜线暴力拆成一个一个点即可。

接下来讲满分做法。

如果只有横线或竖线，那么总面积是好求的，如果只有斜线也可以将它们暴力合并，算出总面积，考虑如何将这两部分合并。

事实上，由于斜线的性质，一条斜线最多只会与一条横线或竖线的一个点相交，显然这个点是好求的，但是如果一条斜线与多条横线或竖线相交在同一个位置就会算重，所以可以用一个 $\operatorname{map}$ 记录哪些点已经被算过了，答案就是这两部分的面积和减去重叠部分。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

struct node{
	int cnt;
	long long x,X,y;
}l[1000005],e[15];
struct tree{
	int l,r,lazy;
	long long val;
}t[4000005];
bool cmp(node a,node b) {
	return a.y<b.y;
}
long long n,tot,TOT,sum,a[1000005],ans;
map<pair<int,int>,int>Map;
void build(int p,int l,int r) {
	if(l>r) return;
	t[p].l=l,t[p].r=r,t[p].lazy=t[p].val=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p*2,l,mid),build(p*2+1,mid+1,r);
}
void update(int p) {
	if(t[p].lazy) t[p].val=a[t[p].r+1]-a[t[p].l];
	else t[p].val=t[p*2].val+t[p*2+1].val;
}
void change(int p,int L,int R,int cnt) {
	if(t[p].l==L&&t[p].r==R) {
		t[p].lazy+=cnt;
		update(p);
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(R<=mid) change(p*2,L,R,cnt);
	else if(L>mid) change(p*2+1,L,R,cnt);
	else change(p*2,L,mid,cnt),change(p*2+1,mid+1,R,cnt);
	update(p);
}
int main() {
	cin>>n>>n>>n>>n;
	for(int i=1;i<=n;i++) {
		int op,x,X,y,Y;
		cin>>op>>x>>y>>X>>Y;
		if(op==3) e[++sum].x=x,e[sum].X=X,e[sum].y=y;
		else l[++tot*2-1].x=x,l[tot*2-1].X=X,l[tot*2-1].y=y,l[tot*2-1].cnt=1,l[tot*2].x=x,l[tot*2].X=X,l[tot*2].y=Y,l[tot*2].cnt=-1,a[tot*2-1]=x,a[tot*2]=X;
	}
	int cnt=1;
	while(cnt) {
		cnt=0;
		for(int i=1;i<=sum;i++) 
		for(int j=1;j<=sum;j++) 
		if(j!=i&&e[i].y&&e[j].y&&e[i].y-e[i].x==e[j].y-e[j].x) 
		if(e[j].x>=e[i].x&&e[j].X<=e[i].X||e[i].x<=e[j].x&&e[j].x<=e[i].X&&e[i].X<=e[j].X) cnt++,e[i].x=min(e[i].x,e[j].x),e[i].X=max(e[i].X,e[j].X),e[i].y=min(e[i].y,e[j].y),e[j].y=0;
	}
	for(int i=1;i<=sum;i++) {
		if(!e[i].y) continue;
		ans+=e[i].X-e[i].x+1;
		for(int j=1;j<=2*tot;j+=2) {
			long long x=l[j].y-e[i].y+e[i].x,y=l[j].x+e[i].y-e[i].x;
			if(l[j].x==l[j].X&&l[j].x>=e[i].x&&l[j].x<=e[i].X&&y>=l[j].y&&y<=l[j+1].y) {
				if(!Map[make_pair(l[j].x,y)]) Map[make_pair(l[j].x,y)]=1,ans--;
			}
			else if(l[j].y==l[j+1].y&&l[j].y>=e[i].y&&l[j].y<=e[i].y+e[i].X-e[i].x&&x>=l[j].x&&x<=l[j].X) if(!Map[make_pair(x,l[j].y)]) Map[make_pair(x,l[j].y)]=1,ans--;
		}
	}
	for(int i=1;i<=2*tot;i++) {
		l[i].x--;
		if(i&1) l[i].y--,a[i]--;
	}
	sort(a+1,a+1+2*tot),sort(l+1,l+1+2*tot,cmp),TOT=unique(a+1,a+1+2*tot)-a-1,build(1,1,TOT);
	for(int i=1;i<2*tot;i++) {
		int L=lower_bound(a+1,a+TOT+1,l[i].x)-a,R=lower_bound(a+1,a+TOT+1,l[i].X)-a-1;
		change(1,L,R,l[i].cnt),ans+=t[1].val*(l[i+1].y-l[i].y);
	}
	cout<<ans;
    return 0;
}