蒟蒻刚学扫描线 对前两个点 求条玄关
查看原帖
蒟蒻刚学扫描线 对前两个点 求条玄关
965007
SMXChina楼主2025/7/24 17:21
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=7e6+10;

int n,a[N<<1],b[N<<1],c[N<<1],tot,toto,ans;

struct line
{
	int x;
	int l,r;
	int ml,mr;
	int opt;
}lines[N<<1];

struct xds
{
	int sum,len;
}xdses[N<<1];

void lsh()
{
	for(int i=1;i<=2*n;i++) b[i]=a[i];
	sort(b+1,b+2*n+1);
	for(int i=2;i<=2*n;i++)
	{
		if(b[i]!=b[i-1])
		{
			c[++toto]=b[i]-b[i-1];
		}
	}
	tot=unique(b+1,b+2*n+1)-(b+1);
	for(int i=1;i<=2*n;i++) a[i]=lower_bound(b+1,b+2*n+1,a[i])-b;
//	for(int i=1;i<=2*n;i++) cout<<a[i]<<" ";
}

bool cmpx(line a1,line a2)
{
	if(a1.x==a2.x) return a1.opt>a2.opt;
	return a1.x<a2.x;
}

void build(int w,int l,int r)
{
	if(l==r)
	{
		xdses[w].len=c[l];
		return ;
	}
	int mid=(l+r)>>1,ls=w<<1,rs=(w<<1)+1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	xdses[w].len=xdses[ls].len+xdses[rs].len;
//	cout<<"!!!"<<w<<" "<<l<<" "<<r<<" "<<xdses[w].len<<endl;
	return ;
}

void add(int w,int l,int r,int ql,int qr,int k)
{
//	cout<<w<<endl;
	if(ql<=l&&r<=qr)
	{
		xdses[w].sum+=k;
		return ;
	}
	int mid=(l+r)>>1,ls=w<<1,rs=(w<<1)+1;
	if(ql<=mid) add(ls,l,mid,ql,qr,k);
	if(qr>mid) add(rs,mid+1,r,ql,qr,k);
	return ;
}

int getsum(int w,int l,int r)
{
	if(l==r&&xdses[w].sum==0) return 0;
	int mid=(l+r)>>1,ls=(w<<1),rs=(w<<1)+1;
	if(xdses[w].sum>0)
	{
//		cout<<"*********"<<w<<" "<<l<<" "<<r<<11111111<<endl;
		return xdses[w].len;
	}
	else return getsum(ls,l,mid)+getsum(rs,mid+1,r);
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		lines[i].x=x1,lines[i].l=y1,lines[i].r=y2,lines[i].opt=1;
		lines[i+n].x=x2,lines[i+n].l=y1,lines[i+n].r=y2,lines[i+n].opt=-1;
		a[(i-1)*2+1]=y1,a[(i-1)*2+2]=y2;
	}
	lsh();
//	cout<<"^^^^";
//	for(int i=1;i<tot;i++) cout<<c[i]<<endl;
	for(int i=1;i<=n;i++)
	{
		lines[i+n].ml=lines[i].ml=a[(i-1)*2+1],lines[i+n].mr=lines[i].mr=a[(i-1)*2+2];
	}
	sort(lines+1,lines+2*n+1,cmpx);
	build(1,1,tot-1);
	for(int i=1;i<2*n;i++)
	{
		add(1,1,tot-1,lines[i].ml,lines[i].mr-1,lines[i].opt);
//		cout<<"$$$"<<lines[i].ml<<" "<<lines[i].mr<<endl;
		ans+=(lines[i+1].x-lines[i].x)*getsum(1,1,tot-1);
//		cout<<lines[i+1].x-lines[i].x<<" "<<getsum(1,1,tot)<<" "<<ans<<endl;
	}
	cout<<ans;
	return 0;
}
2025/7/24 17:21
加载中...