蓝桥第八届 A组油漆面积

╰+攻爆jí腚メ 2022-03-06 11:48 139阅读 0赞

该题有很多种做法，乱搞可以过，最好的方法应该是扫描线，本题是扫描线模板题

官网数据第一个错了，所以83分就是满分

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e4+10;
    #define mp(x,y) make_pair(x,y) 
    #define fir first 
    #define sec second 
    
    struct SEG {
    	int l, r, h, s;
    	SEG(){}
    	SEG(int _l, int _r, int _h, int _s){
    		l=_l; r=_r; h=_h; s=_s;
    	}
    }seg[2*N];
    int p[2*N], cnt=0;
    
    bool cmp(SEG a, SEG b){//从下往上扫描
    	return a.h<b.h;
    }
    
    struct node{
    	int num, len;//num是线段的个数，-1代表两个子节点个数不一致。
    }tree[N<<2];
    
    void build(int rt, int l, int r){
    	tree[rt].num=0;
    	tree[rt].len=0;
    	if(l==r) return;
    	int mid=(l+r)>>1;
    	build(rt<<1, l, mid);
    	build(rt<<1|1, mid+1, r);
    }
    
    void pushdown(int rt, int l, int r){
    	
    	if(tree[rt].num!=-1){
    		tree[rt<<1].num=tree[rt<<1|1].num=tree[rt].num;
    		int mid=(l+r)>>1;
    		if(tree[rt].num){
    			tree[rt<<1].len=p[mid+1]-p[l];
    			tree[rt<<1|1].len=p[r+1]-p[mid+1];
    		}
    		else{
    			tree[rt<<1].len=tree[rt<<1|1].len=0;
    		}
    	}
    	
    } 
    
    void pushup(int rt){
    	
    	if(tree[rt<<1].num==-1 || tree[rt<<1|1].num==-1 || tree[rt<<1].num!=tree[rt<<1|1].num)
    		tree[rt].num=-1;
    	else
    		tree[rt].num=tree[rt<<1].num;
    	
    	tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
    }
    
    void upd(int rt, int l, int r, int L, int R, int s){
    	
    	if(L<=l && r<=R && tree[rt].num!=-1){
    		
    		tree[rt].num+=s;
    		if(tree[rt].num)
    			tree[rt].len=p[r+1]-p[l];
    		else tree[rt].len=0;
    		return;
    	}
    	
    	pushdown(rt, l, r);
    	
    	int mid=(l+r)>>1;
    	if(L<=mid)
    		upd(rt<<1, l, mid, L, R, s);
    	if(R>mid)
    		upd(rt<<1|1, mid+1, r, L, R, s);
    	
    	pushup(rt);
    }
    
    int main(){
    	int n;
    	scanf("%d", &n);
    	
    	for(int i=1; i<=n; i++){
    		int x1, y1, x2, y2;
    		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    		if(x1>x2) swap(x1, x2);
    		if(y1>y2) swap(y1, y2);
    		seg[++cnt]=SEG(x1,x2,y1,1);
    		p[cnt]=x1;
    		seg[++cnt]=SEG(x1,x2,y2,-1);
    		p[cnt]=x2;
    	}
    	
    	sort(p+1, p+1+cnt);
    	sort(seg+1, seg+1+cnt, cmp);
    	
    	int m=unique(p+1, p+1+cnt)-p-1;
    
    	build(1, 1, m);
    	
    	int ans=0, pre=0;
    	for(int i=1; i<=cnt; i++){
    		ans+=(seg[i].h-pre)*tree[1].len;
    	
    		pre=seg[i].h;
    		int l=lower_bound(p+1, p+1+m, seg[i].l)-p;
    		int r=lower_bound(p+1, p+1+m, seg[i].r)-p;
    		
    		if(l<r)
    			upd(1, 1, m, l, r-1, seg[i].s);	//这个地方用r-1的原因是
    //如果要算p[3]-p[1]的长度，会被分成p[2]-p[1] + p[3]-p[3] 这样的话p[3]-p[2]是没有被
    算上的，所以我们统一用p[r+1]-p[l],使区间连续起来。所以初始化的时候就需要r-1操作
    	}
    	printf("%d\n", ans);
    	
    	return 0;
    }