扫描线记录

· · 个人记录

做法

以 P5490 扫描线模板来说。
从题解区盗取一张图（没找到比这更清晰的图）：

可以看到这些图形被一条条纵线划分成了几个规则的矩形。

每一个矩形，都有两条竖线分别代表起始和终点。

所以可以在读入的时候就对始边和终边进行标记。

按横坐标升序，依次处理这些竖线。

处理的时候，考虑到多条边可能在同一横坐标上，每到达一个横坐标（有边存在），就记录当前坐标有多少个点被覆盖。

具体的说，就是遇到一条始边，就将这条边所覆盖的点标记上，代表当前坐标这些点被覆盖，遇到一条终边，就将这条边对应的点取消标记，代表一个矩形的结束。

值域很大，所以要离散化开个权值线段树完成标记。

至于答案，每到一个有边存在的横坐标时，答案就加上（当前横坐标被标记的点数，相当于当前坐标所有始边组合起来之后的长度）乘（下一个有边存在的横坐标减去当前横坐标）

用括号方便看。

完结

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    typedef __int128 ll128;
    const int maxn=1e5+5;
    struct OD
    {
        int x,y1,y2;
        int flag;//权值
        //x是纵线的横坐标，y1是下纵坐标，y2是上纵坐标
    }od[maxn<<1],lsh[maxn<<1];
    //od存储原始读入的竖线信息，lsh存储横坐标不变，纵坐标离散化之后的信息
    int n;
    int h_rem[maxn<<1];//暂时存储纵坐标相关信息
    inline bool cmp(OD a,OD b)
    {
        return (a.x!=b.x)?(a.x<b.x):(a.flag>b.flag);
    }
    struct Tree
    {
        int l,r,ls,rs,len,lazy;
    }tree[maxn*16];//nlogn*2
    int val[maxn<<1];
    int ncnt;
    inline int ls(int i)
    {
        return tree[i].ls;
    }
    inline int rs(int i)
    {
        return tree[i].rs;
    }
    inline int len(int i)
    {
        return tree[i].r-tree[i].l+1;
    }
    inline void add(int i,int val)
    {
        tree[i].lazy+=val;
    }
    inline void push_up(int i)
    {
        if(tree[i].lazy)
        {
            tree[i].len=val[tree[i].r+1]-val[tree[i].l];
            return;
        }
        tree[i].len=tree[ls(i)].len+tree[rs(i)].len;
    }
    int build(int i,int l,int r)
    {
        i=++ncnt;
        tree[i].l=l,tree[i].r=r;
        if(l==r)return i;
        int mid=(l+r)>>1;
        tree[i].ls=build(ls(i),l,mid);
        tree[i].rs=build(rs(i),mid+1,r);
        return i;
    }
    inline void modify(int i,int l,int r,int val)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            add(i,val);
            push_up(i);
            return;
        }
        if(tree[i].r<l||tree[i].l>r)return;
        int mid=(tree[i].l+tree[i].r)>>1;
        if(mid>=l)modify(ls(i),l,r,val);
        if(mid<r)modify(rs(i),l,r,val);
        push_up(i);
    }
    void main()
    {
        scanf("%d",&n);

        int x_1,y_1,x_2,y_2;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
            od[i].x=x_1,od[i].y1=y_1,od[i].y2=y_2,od[i].flag=1;
            od[i+n].x=x_2,od[i+n].y1=y_1,od[i+n].y2=y_2,od[i+n].flag=-1;
            h_rem[i]=y_1;
            h_rem[i+n]=y_2;
        }
        sort(h_rem+1,h_rem+2*n+1);
        int tot=unique(h_rem+1,h_rem+2*n+1)-h_rem-1;
        for(int i=1;i<=2*n;i++)
        {
            lsh[i].x=od[i].x;
            lsh[i].flag=od[i].flag;
            lsh[i].y1=lower_bound(h_rem+1,h_rem+tot+1,od[i].y1)-h_rem;
            lsh[i].y2=lower_bound(h_rem+1,h_rem+tot+1,od[i].y2)-h_rem;
            val[lsh[i].y1]=od[i].y1;
            val[lsh[i].y2]=od[i].y2;
        }
        sort(lsh+1,lsh+2*n+1,cmp);
        int rt=build(1,1,2*n);
        ll128 ans=0;
        for(int i=1;i<2*n;i++)
        {
            modify(1,lsh[i].y1,lsh[i].y2-1,lsh[i].flag);
            ans+=(ll128)tree[1].len*(ll128)(lsh[i+1].x-lsh[i].x);
        }
        printf("%lld",(ll)ans);
    }
}
int main()
{
    Main::main();
    return 0;
}