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

bool cmp(xd xx1,xd xx2){
	return xx1.h<xx2.h;
}

void build(int id,int l,int r){
	tree[id].l=l; tree[id].r=r;
	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 zt){
	if(tree[id].l>r || tree[id].r<l) return;
	else if(tree[id].l>=l&& tree[id].r<=r){
		tree[id].cnt+=zt;
		if(tree[id].cnt==0) tree[id].len=tree[id*2+1].len+tree[id*2].len;
		else tree[id].len=tree[id].r-tree[id].l+1;
		return;
	}
	update(id*2,l,r,zt); update(id*2+1,l,r,zt);
	if(tree[id].cnt==0) tree[id].len=tree[id*2+1].len+tree[id*2].len;
	else 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;
	}
	
	sort(a+1,a+1+2*n,cmp);
	build(1,1,maxv);
	update(1,a[1].lx,a[1].rx,a[1].zt);
	now=a[1].h;
	for(int i=2;i<=2*n;i++){
		ans+=1ll*tree[1].len*(a[i].h-now);
		now=a[i].h;
		update(1,a[i].lx,a[i].rx,a[i].zt);
	}
	cout<<ans;
	return 0;
}
2024/1/26 14:59
加载中...