自动搬运

查看原文

来自洛谷，原作者为

	中二病 **

搬运于2025-08-24 21:53:38，当前版本为作者最后更新于2019-04-27 20:43:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

扫描线，用线段树维护。
把每个矩形左边界和右边界存储，给左边界赋值1，右边界赋值-1，把线段排序，然后依次处理每个线段，给线段所在的区间加上付的值，把每个值>0的区间加到ans里就是当前被矩形覆盖的线的长度，再乘上距离下一个线段之间的距离，就是这两个线段之间覆盖矩形的面积。
然后考虑用线段树处理。先想到用lazy_tag进行区间修改，但其实只有+1和-1的操作并且都是成对出现的，所以只要在push_up的时候对cnt[i]>0的i区间更新sum即可

if(cnt[qaq])
sum[qaq]=r-l+1;
else sum[qaq]=sum[left(qaq)]+sum[right(qaq)];

然后这个题坐标全是整数且数据不大，所以偷个懒不用离散化

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
struct pg
{
	int x;
	int y1;
	int y2;
	int flag;
}line[N*5];
int cnt[N*10],sum[N*10];
int n;
bool cmp(pg a,pg b)
{
	return a.x<b.x;
}
int left(int qaq)
{
	return qaq<<1;
}
int right(int qaq)
{
	return qaq<<1|1;
}
void push_up(int qaq,int l,int r)
{
	if(cnt[qaq])
		sum[qaq]=r-l+1;
	else sum[qaq]=sum[left(qaq)]+sum[right(qaq)];
}
void change(int qaq,int l,int r,int nl,int nr,int k)
{
	if(nl<=l&&nr>=r)
	{
		cnt[qaq]+=k;
		push_up(qaq,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	if(nl<=mid)change(left(qaq),l,mid,nl,nr,k);
	if(nr>mid)change(right(qaq),mid+1,r,nl,nr,k);
	push_up(qaq,l,r);
}
int main()
{
	cin>>n;
	int X1,X2,Y1,Y2;
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
		if(X1>X2)swap(X1,X2);
		if(Y1>Y2)swap(Y1,Y2);
		if (X1==X2)
		{
             line[++tot].x=X1-1;line[tot].y1=Y1;line[tot].y2=Y2;line[tot].flag=1;
             line[++tot].x=X2+1;line[tot].y1=Y1;line[tot].y2=Y2;line[tot].flag=-1;
         }
		 else
		 {
             line[++tot].x=X1;line[tot].y1=Y1-1;line[tot].y2=Y2+1;line[tot].flag=1;
             line[++tot].x=X2;line[tot].y1=Y1-1;line[tot].y2=Y2+1;line[tot].flag=-1;
         }
	}
	sort(line+1,line+tot+1,cmp);
	int ans=0;
	for(int i=1;i<=tot;i++)
	{
		//cout<<sum[1]<<endl;
			ans+=sum[1]*(line[i].x-line[i-1].x);
			change(1,0,100010,line[i].y1,line[i].y2-1,line[i].flag);
	}
	cout<<ans;
	return 0;
}

如果要进行离散化，对所有的x值排序并去重，标上序号，用c[i]表示序号为i的x值，然后再push_up时改成sum[qaq]=c[r]-c[l]+1即可