P5490 【模板】扫描线

扫描线模板，注意点在注释里

注意数组大小

code：

#include<bits/stdc++.h>
#define gc getchar
#define ll long long
using namespace std;
const ll N=1e5+7;
template <class I>
inline void read(I &x) {
    ll f=1;
    char c;
    for(c=gc(); c<'0'||c>'9'; c=gc()) if(c=='-') f=-1;
    for(x=0; c>='0'&&c<='9'; x=(x<<3)+(x<<1)+(c&15),c=gc());
    x*=f;
}
ll n,tot,ans;
ll raw[N<<1];
struct tree {
    ll l,r,cnt;
    ll len;
} t[N<<3];
void build(ll p,ll l,ll r) {
    t[p].l=l,t[p].r=r,t[p].cnt=t[p].len=0;
    if(l==r) return;
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);
    build((p<<1)+1,mid+1,r);
}
inline void upt(ll p) {
    if(t[p].l==t[p].r) t[p].len=t[p].cnt>0?raw[t[p].r+1]-raw[t[p].l]:0;//不可以忘记特判叶子节点嗷
    else if(t[p].cnt) t[p].len=raw[t[p].r+1]-raw[t[p].l];
    else t[p].len=t[P*2+1].len+t[P*2].len;
}
void change(ll p,ll r,ll k) {
    if(t[p].l>=l&&t[p].r<=r) {
        t[p].cnt+=k;
        upt(p);
        return;
    }
    ll mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(P*2,k);
    if(r>mid) change(P*2+1,k);
    upt(p);
}
struct edge {
    ll x,yy1,yy2,k;
    bool operator < (const edge &a) const {
        return x<a.x;
    }
} e[N<<3];
inline ll val(ll x) {
    return lower_bound(raw+1,raw+1+tot,x)-raw;
}
int main() {
    read(n);
    for(ll i=1; i<=n; i++) {
        ll xx1,xx2,yy2;
        read(xx1),read(yy1),read(xx2),read(yy2);
        e[(i<<1)-1].x=xx1,e[(i<<1)-1].yy1=yy1,e[(i<<1)-1].yy2=yy2,e[(i<<1)-1].k=1;
        e[i<<1].x=xx2,e[i<<1].yy1=yy1,e[i<<1].yy2=yy2,e[i<<1].k=-1;
        raw[++tot]=yy1;
        raw[++tot]=yy2;
    }
    sort(raw+1,raw+1+tot);
    tot=unique(raw+1,raw+1+tot)-raw-1;
    for(ll i=1; i<=n; i++) {
        e[(i<<1)-1].yy1=val(e[(i<<1)-1].yy1),e[(i<<1)-1].yy2=val(e[(i<<1)-1].yy2);
        e[i<<1].yy1=val(e[i<<1].yy1),e[i<<1].yy2=val(e[i<<1].yy2);
    }
    sort(e+1,e+1+2*n);
    build(1,1,tot);
    for(ll i=1; i<=2*n; i++) {
        change(1,e[i].yy1,e[i].yy2-1,e[i].k);
        ans+=t[1].len*(e[i+1].x-e[i].x);
    }
    cout<<ans<<endl;
    return 0;
}
就这_^^