P5490后八个点每次都是建树时候递归RE求调玄关
查看原帖
P5490后八个点每次都是建树时候递归RE求调玄关
586905
Linge_Zzzz一辈子乐队楼主2023/8/11 09:16
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int long long
const int N=1e5+10;

int n,X[N*2];

struct Line
{
	int y,l,r,w;
	bool operator<(Line b)
	{
		return y<b.y;
	}
	Line(int yy,int ll,int rr,int ww)
	{
		y=yy,l=ll,r=rr,w=ww;
	}
	Line(){}
}line[N*2];

struct node
{
	int l,r;
	int sum,len;
}t[N*4];

void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	t[p].len=0,t[p].sum=0;
	if(l==r)return;
	int m=(l+r)>>1;
	build(p*2,l,m);
	build(p*2+1,m+1,r);
	return;
}

void pushup(int p)
{
	int l=t[p].l,r=t[p].r;
	if(t[p].sum)t[p].len=X[r+1]-X[l];
	else t[p].len=t[p*2].len+t[p*2+1].len;
}

void update(int p,int L,int R,int c)
{
	int l=t[p].l,r=t[p].r;
	if(X[r+1]<=L||R<=X[l])return;
	if(L<=X[l]&&X[r+1]<=R)
	{
		t[p].sum+=c;
		pushup(p);
		return;
	}
	update(p*2,L,R,c);
	update(p*2+1,L,R,c);
	pushup(p);
}

signed main()
{
//	freopen("in.txt","r",stdin);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		int x1,y1,x2,y2;
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		X[2*i-1]=x1,X[2*i]=x2;
		line[2*i-1]=Line(y1,x1,x2,1);
		line[2*i]=Line(y2,x1,x2,-1);
	}
	n<<=1;
	sort(line+1,line+1+n);
	sort(X+1,X+n+1);
	int tot=unique(X+1,X+n+1)-X-1;
	build(1,1,tot-1);
	int ans=0;
	for(int i=1;i<n;i++)
	{
		update(1,line[i].l,line[i].r,line[i].w);
		ans+=t[1].len*(line[i+1].y-line[i].y);
	}
	printf("%lld\n",ans);
	return 0;
}
2023/8/11 09:16
加载中...