[数据结构与算法]1228. 油漆面积 （扫描线 线段树 模板

添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+9;
struct  node
{
    int x,y1,y2;
    int cover;
    bool operator <(const node &t)const{
        return x<t.x;
    }
}t[N*2];
struct segment
{
    int l,r;
    int cnt;
    int len;
    
}tr[N*8];
void build(int u,int l,int r){//把边建好
    if(l==r)tr[u]={l,r};
    else {
        int mid=l+r>>1;
        tr[u]={l,r};
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
    }
}
void pushup(int u){
    //如果当前点覆盖  把当前的线算出
    if(tr[u].cnt)tr[u].len=tr[u].r-tr[u].l+1;
    //如果是结点 则返回0
    else if(tr[u].l==tr[u].r)tr[u].len=0;
    //否则返回根等于子树的和
    else tr[u].len=tr[u*2].len+tr[u*2+1].len;
}
void modify(int u,int l,int r,int k){
    if(tr[u].l>=l&&tr[u].r<=r){
        //如果包括了 把当前的点修改
        tr[u].cnt+=k;
        pushup(u);//父节点修改
    }
    else {
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid){
            modify(u*2,l,r,k);
        }
        if(r>mid)modify(u*2+1,l,r,k);
        pushup(u);
    }
}
int m;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        t[++m]={x1,y1,y2,1};//当前入边
        t[++m]={x2,y1,y2,-1};//当前出边
    }
    // for(int i=1;i<=m;i++)cout<<t[i].x<<endl;
    sort(t+1,t+1+m);
    // for(int i=1;i<=m;i++)cout<<t[i].x<<endl;
    build(1,0,10000);//建立线段树
    int ans=0;
    for(int i=1;i<=m;i++){
        // cout<<t[i].x<<endl;
        if(i>1)ans+=tr[1].len*(t[i].x-t[i-1].x);
        modify(1,t[i].y1,t[i].y2-1,t[i].cover);//修改出边还是入边
        //y2-1是因为线段树不能重合
    }
    cout<<ans<<endl;

    return 0;
}