全紫求调
查看原帖
全紫求调
476487
tangml楼主2024/8/22 09:50
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2e5+100;//一个矩阵两个点 

struct SegmentTree{
	int cnt,len;
}tr[N*8];//pushup操作时可能访问到叶子节点 

struct Line{
	int l,r,high;
	int flag;
}line[N*2];

int n,m,idx=1;
int ans;

void pushup(int p,int lens)
{
	if(tr[p].cnt)	tr[p].len=lens;
	else	tr[p].len=tr[p*2].len+tr[p*2+1].len;
} 

void change(int p,int l,int r,int nowl,int nowr,int k)
{
	if(!p)	p=++idx;
	if(l<=nowl && nowr<=r)
	{
		tr[p].cnt+=k;
		pushup(p,nowr-nowl+1);
		return;
	}
	int mid=nowl+nowr>>1;
	if(l<=mid)	change(p*2,l,r,nowl,mid,k);
	if(r>mid)	change(p*2+1,l,r,mid+1,nowr,k);
	pushup(p,nowr-nowl+1);
}

signed main()
{
	int minx=1e18,maxx=-1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		line[2*i-1]={x1,x2,y1,1};
		line[2*i]={x1,x2,y2,-1};
		minx=min(minx,y1),maxx=max(maxx,y2);
	}
	
	n<<=1;
	sort(line+1,line+n+1,[&](Line a,Line b){
		return a.high<b.high;
	});
	
	for(int i=1;i<n;i++)
	{
		change(1,line[i].l,line[i].r-1,minx,maxx,line[i].flag);
		ans+=tr[1].len*(line[i+1].high-line[i].high);
	}
	
	cout<<ans<<endl;
	
	return 0;
}
2024/8/22 09:50
加载中...