扫描线

#include 
#define int long long
using namespace std;

int read()
{
	int res=0,p=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')p=-1; ch=getchar();}
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return res*p;
}

const int maxn=1e6+10;

int n,num[maxn],cnt;
int sum[maxn<<3],add[maxn<<3];
unsigned long long ans=0;

struct note {int x,yl,yr,flag;}ed[maxn];

bool cmp(note a,note b)
{
	if(a.x==b.x) return a.yl0) add[id]=num[r]-num[l];
	else add[id]=add[id*2]+add[id*2+1];
}

void modify(int id,int l,int r,int x,int y,int v)
{
	if(x>=r||y<=l) return ;
	if(l>=x&&r<=y)  return (sum[id]+=v,pushup(id,l,r),void());
	int mid=(l+r)/2;
	modify(id*2,l,mid,x,y,v),modify(id*2+1,mid,r,x,y,v);
	pushup(id,l,r);
}

signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		int a=read(),b=read(),c=read(),d=read();
		num[++cnt]=b,ed[cnt].x=a,ed[cnt].yl=b,ed[cnt].yr=d,ed[cnt].flag=1;
		num[++cnt]=d,ed[cnt].x=c,ed[cnt].yl=b,ed[cnt].yr=d,ed[cnt].flag=-1;
	}
	sort(ed+1,ed+1+cnt,cmp),sort(num+1,num+cnt+1);
	int siz=unique(num+1,num+cnt+1)-num-1;
	for(int i=1;i<=cnt;++i) ed[i].yl=lower_bound(num+1,num+siz+1,ed[i].yl)-num,ed[i].yr=lower_bound(num+1,num+siz+1,ed[i].yr)-num;
	for(int i=1;i