1,5,6wa了,求调
查看原帖
1,5,6wa了,求调
1116724
Chitose_楼主2024/1/26 16:01
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
struct node{
	int cnt,l,r;
	int len;
}tree[maxn*8];
struct xd{
	int lx,rx,zt;
	int h;
}a[maxn*4];
int n,xx,xxx,maxv,now;
int yy,yyy;
long long ans;

bool cmp(xd xd1,xd xd2){
	return xd1.h<xd2.h;
}

void build(int id,int l,int r){
	tree[id].l=l; tree[id].r=r; tree[id].cnt=0; tree[id].len=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
}

void update(int id,int l,int r,int val){
	if(tree[id].l>r || tree[id].r<l) return;
	if(tree[id].l>=l && tree[id].r<=r){
		tree[id].cnt+=val;
		if(tree[id].cnt==0) tree[id].len=tree[id*2+1].len+tree[id*2].len;
		else if(tree[id].cnt>0) tree[id].len=tree[id].r-tree[id].l+1;
		return;
	}
	update(id*2,l,r,val); update(id*2+1,l,r,val);
	if(tree[id].cnt==0) tree[id].len=tree[id*2+1].len+tree[id*2].len;
	else if(tree[id].cnt>0) tree[id].len=tree[id].r-tree[id].l+1;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&xx,&yy,&xxx,&yyy);
		if(xx>xxx){
			swap(xx,xxx);
		}
		maxv=max(maxv,xxx);
		a[i*2-1].h=min(yy,yyy); a[i*2-1].lx=xx; a[i*2-1].rx=xxx-1; a[i*2-1].zt=1;
		a[i*2].h=max(yy,yyy); a[i*2].lx=xx; a[i*2].rx=xxx-1; a[i*2].zt=-1;
	}
	n*=2;
	sort(a+1,a+1+n,cmp);
	build(1,1,maxv);
	for(int i=1;i<=n;i++){
		update(1,a[i].lx,a[i].rx,a[i].zt);
		ans+=1ll*tree[1].len*(a[i+1].h-a[i].h);	
	}
	cout<<ans;
	return 0;
}
2024/1/26 16:01
加载中...