为啥全RE?
查看原帖
为啥全RE?
292801
zhong0204楼主2021/2/22 21:15
#include <iostream>
#include <algorithm>
using namespace std;
#define M 100010
#define ll long long

int n,X[M];

struct scanline{
	int l,r,h,flag;
	scanline(int l0=0,int r0=0,int h0=0,int f0=0){
		l=l0,r=r0,h=h0,flag=f0;
	}
}line[M];

struct stree{
	stree *lson,*rson;
	int l,r,len,sum;
	stree(){
		l=r=len=sum=0;
	}
}*root = new stree;

bool cmp(scanline x,scanline y){
	return x.h<y.h;
}

void build(stree *tree,int l,int r){
	tree->l=l,tree->r=r;
	if(l==r)
		return ;
	tree->lson = new stree;
	tree->rson = new stree;
	int mid=(l+r)>>1;
	build(tree->lson,l,mid);
	build(tree->rson,mid+1,r);
	return ;
}

void change(stree *tree,int x,int y,int flag){
	if(X[tree->r+1]<=x||y<=X[tree->l])
		return ;
	if(x<=X[tree->l]&&X[tree->r+1]<=y){
		tree->sum+=flag;
		if(tree->sum)
			tree->len=X[tree->r+1]-X[tree->l];
		else
			tree->len=tree->lson->len+tree->rson->len;
		return ;
	}
	change(tree->lson,x,y,flag);
	change(tree->rson,x,y,flag);
	if(tree->sum)
		tree->len=X[tree->r+1]-X[tree->l];
	else
		tree->len=tree->lson->len+tree->rson->len;
	return ;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		line[2*i-1]=scanline(x1,x2,y1,1);
		line[2*i]=scanline(x1,x2,y2,-1); 
		X[2*i-1]=x1,X[2*i]=x2;
	}
	n<<=1;
	sort(line+1,line+n+1,cmp);
	//for(int i=1;i<=n;i++) cout<<line[i].h<<" ";
	//cout<<endl;
	sort(X+1,X+n+1);
	//for(int i=1;i<=n;i++) cout<<X[i]<<" ";
	int tot = unique(X+1,X+n+1)-X-1;
	build(root,1,tot-1);
	long long ans=0;
	for(int i=1;i<=n-1;i++){
		change(root,line[i].l,line[i].r,line[i].flag);
		ans+=root->len*(line[i+1].h-line[i].h);
	}
	cout<<ans<<endl;
	return 0;
}
2021/2/22 21:15
加载中...