【模板】扫描线

洛咕

题意:求\(n(n<=10^5)\)个矩形的面积并.一个矩形的左下角坐标为 \((x_1, y_1)\)，右上角坐标为 \((x_2, y_2)\)\((0<=x_1,x_2,y_1,y_2<=1e9)\).

分析:敷衍一下,挂一个洛咕题解的链接

也不晓得为啥,写扫描线的话,数组反正要开离奇地大,然后一定要开long long.反正我一直把数组加大,加着加着就过了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e6+5;//离奇地大 就行
ll a[N],raw[N];//全部开long long
struct line{ll x,y1,y2,k;}e[N];
struct xd_tree{ll len,cnt;}t[N<<1];
inline bool cmp(const line &x,const line &y){
    return x.x==y.x?x.y1<y.y1:x.x<y.x;
}
inline void pushup(ll p,ll l,ll r){
    if(t[p].cnt>0)t[p].len=raw[r+1]-raw[l];
    else t[p].len=t[p<<1].len+t[p<<1|1].len;
}
inline void change(ll p,ll l,ll r,ll ql,ll qr,ll val){
    if(ql<=l&&r<=qr){
        t[p].cnt+=val;
        pushup(p,l,r);
        return;
    }
    ll mid=(l+r)>>1;
    if(ql<=mid)change(p<<1,l,mid,ql,qr,val);
    if(qr>mid)change(p<<1|1,mid+1,r,ql,qr,val);
    pushup(p,l,r);
}
int main(){
    ll n=read(),tot=0;
    for(ll i=1;i<=n;++i){
        ll x1=read(),y1=read(),x2=read(),y2=read();
        e[(i<<1)-1].x=x1;e[(i<<1)-1].y1=y1;e[(i<<1)-1].y2=y2;e[(i<<1)-1].k=1;
        e[i<<1].x=x2;e[i<<1].y1=y1;e[i<<1].y2=y2;e[i<<1].k=-1;
        a[++tot]=y1;a[++tot]=y2;//离散化用的数组
    }
    sort(a+1,a+tot+1);
    ll sum=unique(a+1,a+tot+1)-a-1;
    n<<=1;
    for(int i=1;i<=n;++i){
        ll pos1=lower_bound(a+1,a+sum+1,e[i].y1)-a;
        ll pos2=lower_bound(a+1,a+sum+1,e[i].y2)-a;
        raw[pos1]=e[i].y1;raw[pos2]=e[i].y2;//映射
        e[i].y1=pos1;e[i].y2=pos2;
    }
    sort(e+1,e+n+1,cmp);//按照横坐标从小到大排序
    ll ans=0;
    for(int i=1;i<=n;++i){
        change(1,1,n,e[i].y1,e[i].y2-1,e[i].k);//线段树
        ans+=1ll*t[1].len*(e[i+1].x-e[i].x);//统计答案:长乘宽
    }
    printf("%lld\n",ans);
    return 0;
}

【模板】扫描线

原文：https://www.cnblogs.com/PPXppx/p/11522272.html