题解：P5490 【模板】扫描线 & 矩形面积并

· · 题解

前排提醒：本题要求先掌握线段树和离散化。

算法介绍：

扫描线，顾名思义，一段线在平面上扫。一般用于解决图形的周长和面积问题。

给一张动图（引用自 oiwiki）：

观察整个过程不难看出，我们实际上可以这么求图形的面积：

即，用一条红线不断扫描，把整个图形分成不同的小矩形，扫过的距离为小矩形的高，只需要知道每个小矩形的宽就能求得整个图形的面积。

如何求得小矩形的宽？

如果遇到矩形下方的边，就将该线段所代表的区间加一，如果是矩形上方的边就减一。

最后，数轴上大于零的位置证明被覆盖，需要计算，而等于零就证明没有被覆盖，显然不能小于零（可以看看动图中的 cnt 数组）。得到所有大于零的位置覆盖的总区间长度后，我们也就得到了要求的小矩形的宽（实际上矩形的说法并不严谨，但通过平移，要求的每个小形状可以等价于一个矩形）。

而我们要求得每个矩形的宽，所需要做的事情等价于两个操作：

  1. 区间加减；
  2. 统计该数组上有多少位置不为 0。

用线段树维护即可。

然后我们注意到数据范围达到了 10^9，所以还需要离散化。

复杂度证明：

如果使用 map 离散化的话，所需的时间复杂度为 O(n\log n)；

线段树的复杂度为 O(n\log n)。

总时间复杂度 O(n\log n)，可以通过此题。

代码细节：

如果直接套用线段树模板（如 P3372），不久应该会发现有点难处理。

具体说明一下线段树的操作：每个位置维护两个数据，一个是在该区间范围内覆盖的长度 c，第二个是该段被完全覆盖的次数 tag。

每次修改时，若完全覆盖，则修改 tag，否则修改左右两子区间。

若 tag 不为零，c 的值为该节点维护区间长度；若 tag 为零，则 c 的值为左右两子节点的 c 值之和（该区间没有被完全覆盖不代表该区间的子区间没有被覆盖）。

这里也验证了我们上文提及的线段树时间复杂度为 O(n \log n)：c 仅由 tag 决定，不影响复杂度。而修改 tag 的单次时间复杂度显然为 O(\log n)。

还需要提及的一点就是，由于本题维护的是点，线段树维护区间 [l,r] 时，实际上维护的是 [l,r+1]。

举个例子，区间 [1,3] 由 [1,2] 和 [3,3] 组成。

这显然不对。[2,3] 这一段被漏掉了。

而采用我们上面提到的修正方法，区间 [1,3] 由 [1,2] 表示，两个子区间在线段树上分别为 [1,1] 和 [2,2]，也就是实际上的 [1,2] 和 [2,3]。

最后提醒：记得开 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int x,sy,ey,tag;
}line[100005<<1];
map<int,int>mp;
int cnt;
int R[1000005];
int b[200005];
bool cmp(node a,node b){
    if(a.x==b.x)return a.tag>b.tag;
    return a.x<b.x;
}
struct T{
    int c,tag;
}tree[400005<<2];
void pushup(int p,int l,int r){
    if(!tree[p].tag){
        tree[p].c=tree[p<<1].c+tree[p<<1|1].c;
        return;
    }
    tree[p].c=R[r+1]-R[l];
}
void update(int p,int l,int r,int ql,int qr,int k){
    if(l>qr||r<ql)return;
    if(l>=ql&&r<=qr){
        tree[p].tag+=k;
        if(tree[p].tag)tree[p].c=R[r+1]-R[l];
        else pushup(p,l,r);
        return;
    }
    int mid=l+r>>1;
    update(p<<1,l,mid,ql,qr,k);
    update(p<<1|1,mid+1,r,ql,qr,k);
    pushup(p,l,r);
}
signed main(){
    int n;
    cin>>n;
    int p=0;
    for(int i=1;i<=n;i++){
        int x,xx,y,yy;
        cin>>x>>y>>xx>>yy;
//      yy--;
        line[++p].x=x;
        line[p].sy=y;
        line[p].ey=yy;
        line[p].tag=1;
        line[++p].x=xx;
        line[p].sy=y;
        line[p].ey=yy;
        line[p].tag=-1;
    }
    n=p;
    p=0;
    for(int i=1;i<=n;i+=2){
        b[++p]=line[i].sy;
        b[++p]=line[i].ey;
    }
    sort(b+1,b+p+1);
    int mcnt=0;
    for(int i=1;i<=p;i++){
        if(!mp[b[i]]){  
            mp[b[i]]=++cnt;
            R[cnt]=b[i];
        }
    }
    for(int i=1;i<=n;i++){
        line[i].sy=mp[line[i].sy];
        line[i].ey=mp[line[i].ey];
    }
    sort(line+1,line+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(i!=1)ans+=tree[1].c*(line[i].x-line[i-1].x);
        update(1,1,cnt,line[i].sy,line[i].ey-1,line[i].tag);
    }
    cout<<ans;
    return 0;
}