扫描线模板全WA求调(悬2关)
查看原帖
扫描线模板全WA求调(悬2关)
373198
WhileTrueRP楼主2024/8/13 11:49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
struct node1{
	int lx,rx,y,type;
}line[N];
struct node2{
	int l,r,sum,cnt;
}tree[N<<2];
int x[N];
bool cmp(node1 x,node1 y){
	return x.y < y.y;
}
void build(int p,int l,int r){
	tree[p].l = x[l];
	tree[p].r = x[r];
	if(r-l <= 1){
		return;
	}
	int mid = (l+r) >> 1;
	build(p<<1,l,mid);
	build(p<<1|1,mid,r);
}
void add(int p,int ll,int rr,int c){
	if(tree[p].l == ll && tree[p].r == rr){
		tree[p].cnt += c;
		if(tree[p].cnt){
			tree[p].sum = tree[p].r - tree[p].l;
		}else{
			tree[p].sum = 0;
		}
		return;
	}
	if(rr <= tree[p<<1].r){
		add(p<<1,ll,rr,c);
	}else if(ll >= tree[p<<1|1].l){
		add(p<<1|1,ll,rr,c);
	}else{
		add(p<<1,ll,tree[p<<1].r,c);
		add(p<<1|1,tree[p<<1|1].l,rr,c);
	}
	if(tree[p].cnt){
		tree[p].sum = tree[p].r - tree[p].l;
	}else{
		tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
	}
}
int main(){
//	freopen("P5490_1.in","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int xa,ya,xb,yb;
		scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
		x[2*i-1] = xa,x[2*i] = xb;
		line[2*i-1] = {xa,xb,ya,1};
		line[2*i] = {xa,xb,yb,-1};
	}
	n <<= 1;
	sort(x+1,x+1+n);
	sort(line+1,line+1+n,cmp);
	build(1,1,n);
	ll ans = 0;
	for(int i=1;i<=n;i++){
		ans += 1ll * tree[1].sum * (line[i].y - line[i-1].y); 
		add(1,line[i].lx,line[i].rx,line[i].type);
	}
	printf("%lld",ans);
}
2024/8/13 11:49
加载中...