P5490 【模板】扫描线

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define deubg_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int T;
struct Line{
    int x,y1,y2,add;
    bool operator <(const Line& o) const{
        return x < o.x;
    }
}line[maxn];int cntL;
int lisa[maxn],tail;
void init(){
    sort(lisa+1,lisa+tail+1);
    tail = unique(lisa+1,lisa+tail+1)-lisa-1;
}
int find(int x){
    return lower_bound(lisa+1,lisa+tail+1,x)-lisa;
}
struct Seg{
    struct node{
        int l,r;
        int cnt;//区间被覆盖的次数
        int len;//当前区间，被覆盖的长度
    }tr[8*200010];
    void build(int l,int r,int u = 1){
        tr[u] = {l,r,0,0};
        if(l == r) return ;
        else{
            int mid = (l+r)>>1;
            build(l,mid,u*2);
            build(mid+1,r,u*2+1);
        }
    }
    void pushup(int u){
        if(tr[u].cnt > 0) tr[u].len = lisa[tr[u].r+1] - lisa[tr[u].l];
        else if(tr[u].l != tr[u].r){
            tr[u].len = tr[u*2].len + tr[u*2+1].len;
        }else{
            tr[u].len = 0;
        }
    }
    void modify(int l,int r,int k,int u = 1){
        if(l<= tr[u].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(l,r,k,u*2);
            if(r>mid) 
                modify(l,r,k,u*2+1);
            pushup(u);
        }
    }
}seg;

int main(){
//    debug_in;

    read(T);    
    while(T--){
        int x1,y1,x2,y2;read(x1,y1,x2,y2);
        lisa[++tail] = y1;
        lisa[++tail] = y2;
        line[++cntL] = {x1,y1,y2,+1};
        line[++cntL] = {x2,y1,y2,-1};
    }
    init();
    sort(line+1,line+cntL+1);
    seg.build(1,tail-1);//需要减1


    ll res = 0;
    for(int i = 1;i<=cntL;i++){
        if(i>1){
            res += (ll)seg.tr[1].len * (line[i].x - line[i-1].x);
        }
        seg.modify(find(line[i].y1),find(line[i].y2)-1,line[i].add);//需要减1，因为统计的是区间，两个相邻区间不能有交点
    }
    printf("%lld\n",res);
    return 0;
}