扫描线求调
  • 板块灌水区
  • 楼主XingnoYi
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/8 16:07
  • 上次更新2023/11/3 05:10:40
查看原帖
扫描线求调
735797
XingnoYi楼主2023/8/8 16:07

20pts

#include <iostream>
#include <algorithm>
#define big long long
using namespace std;
big n;
big st[200005];
struct orz_ypa{
	big x,y1,y2,val;
}q[200005];
bool cmp(orz_ypa l,orz_ypa r)
{
	return l.x < r.x;
}
struct node{
	big l,r,val,ans;
}t[800006];
void build(big l,big r,big id)
{
	t[id].l = l;
	t[id].r = r;
	if(l == r)
	{
		return;
	}
	big mid = (l+r)>>1;
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
}
void up(big id)
{
	if(t[id].val > 0)
	{
		t[id].ans = st[t[id].r+1]-st[t[id].l];
	}
	else
	{
		t[id].ans = t[id*2].ans+t[id*2+1].ans;
	}
}
void update(big l,big r,big va,big id)
{
	if(l <= t[id].l && t[id].r <= r)
	{
		t[id].val += va;
		up(id);
		return;
    }
	big mid = (t[id].l+t[id].r) >> 1;
	if(mid >= l)
	{
		update(l,r,va,id*2);
    }
    if(mid < r)
	{
		update(l,r,va,id*2+1);
    }
    up(id);
}
int main()
{
	cin >> n;
	for(big i = 1;i <= n;i++)
	{
		big a,b,c,d;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		q[i] = {a,b,d,1}, q[i+n]={c,b,d,-1};
		st[i] = b, st[i+n] = d;
	}
	sort(st+1,st+2*n+1);
	big c=1;
	for(big i = 2;i <= 2*n;i++)
	{
		if(st[i-1] != st[i])
		{
			st[++c] = st[i];
		}
	}
	for(big i = 1;i <= 2*n;i++)
	{
		q[i].y1 = lower_bound(st+1,st+c+1,q[i].y1)-st;
		q[i].y2 = lower_bound(st+1,st+c+1,q[i].y2)-st;
	}
	sort(q+1,q+2*n+1,cmp);
	build(1,c,1);
	big sum=0;
	for(big i = 1;i < 2*n;i++)
	{
		update(q[i].y1,q[i].y2-1,q[i].val,1);
		sum += t[1].ans*(q[i+1].x-q[i].x);
	}
	printf("%lld\n",sum);
	return 0;
}
2023/8/8 16:07
加载中...