编译失败,寄,在线等,急
查看原帖
编译失败,寄,在线等,急
938950
YGW6楼主2023/11/12 16:13

//P5490 【模板】扫描线 //YGW6

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e5+5;

int n,m,ans;
int c[N<<1];

struct segment_tree
{
	int l,r,len,cnt;
}t[N<<3];

struct scanline
{
	int x,y1,y2,k;
}y[N<<1];

void push_up(int u)
{
	if(t[u].cnt)
		t[u].len=c[t[u].r+1]-c[t[u].l];
	else if(t[u].l!=t[u].r)
		t[u].len=t[u*2].len+t[u*2+1].len;
	else
		t[u].len=0;
}

bool cmp(scanline a,scanline b)
{
	return a.x<b.x;
}

void build(int u,int l,int r)
{
	t[u].l=l,t[u].r=r;
	if(l==r)
	{
		t[u].len=t[u].cnt=0;
		return;
	}
	int mid=l+r>>2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	push_up(u);
}

int find(int x)
{
	return lower_bound(y+1,y+1+2*n,x)-y;
}

void update(int u,int l,int r,int k)
{
	if(t[u].l>=l&&t[u].r<=r)
	{
		t[u].cnt+=k;
		push_up(u);
		return;
	}
	if(l<t[u].l)
		update(2*u,l,r,k);
	if(r>t[u].r)
		update(2*u+1,l,r,k);
	push_up(u);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1,j=0;i<=n;++i)
	{
		int x1,x2,y1,y2;
		cin>>x1>>x2>>y1>>y2;
		y[++j]={x1,y1,y2,1};
		y[++j]={x2,y1,y2,-1};
		c[++m]=y1;
		c[++m]=y2;
	}
	sort(c+1,c+m+1);
	sort(y+1,y+1+2*n,cmp);
	m=unique(c+1,c+1+m)-c-1;
	build(1,1,m-1);
	for(int i=1;i<2*n;++i)
	{
		update(1,find(y[i].y1),find(y[i].y2)-1,y[i].k);
		ans=ans+1ll*t[1].len*(y[i+1].x-y[i].x);
	}
	cout<<ans;
	return 0;
}
2023/11/12 16:13
加载中...