P5490

Aryper · 2021-08-12 11:02:33 · 个人记录

【模板】扫描线

先离散化坐标，并将每个点代表其上的区间，方便覆盖的修改与查询。

我们考虑矩形的每一条竖边，将其当作一次区间修改，当修改操作的横坐标发生变化时，我们需要查询被覆盖的长度，将长度乘上宽度这个区域被覆盖的面积。

查询和修改容易用线段树实现。

可以使用 lazytag，但是比较麻烦。

可以使用 cnt 统计某个区间被完全覆盖的次数。我们根据这个矩形面积并的性质可以知道，cnt 不仅始终大于等于 0，并且在所有修改结束后都会回到 0，更重要的是，只要这个区间的 cnt>0，这个区间一定是在被覆盖的状态。

那这个性质有什么用呢？它大有用处，有用到可以让我们不使用 lazytag。

我们将某次修改的区间划分出的 \log n 个区间的 cnt 加上 k，以此维护一个信息 len，表示这个区间被覆盖的长度。

那么如果 cnt>0，表示这个区间被完全覆盖，我们的 len 就等于区间长度。

如果 cnt=0，len 就等于两个子节点的并，即 len_p=len_{2p}+len_{2p+1}。

那么为什么交叉的区间之类的情况不会影响该做法的正确性呢？原因就是上述我们提到的性质。

使用 lazytag 就相当于把问题直接视作区间加减，而不使用则是将其看作线段覆盖。

我们覆盖的区间段是莫得问题的，毕竟从矩形的一端到另一端，其间的过程中这个线段无论如何都处于被覆盖状态。所以其间即便有对区域中某些区间的减，并不影响这个区间始终被覆盖的事实。

因此我们针对条线段，只需要关注其被划分出的 \log n 个区域即可，不需要关心这些区间的覆盖是否会被其它交叉区间的覆盖影响，因为只要没到该矩形的最右端，这个区间一定始终处于被覆盖状态。

时间复杂度 O(n\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e6;

struct sgt{
    ll l,r,len,cnt;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define len(x) tree[x].len
    #define cnt(x) tree[x].cnt
}tree[N*8+5];

struct node{
    ll x,ya,yb,k;
}a[N*2+5];

ll n,cnt,totx,toty,xa,xb,ya,yb,ans;

ll uqx[N*2+5],uqy[N*2+5];

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) {return;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);build(p*2+1,mid+1,r);
}

void add(ll p,ll l,ll r,ll k) {
    if(l<=l(p)&&r>=r(p)) {
        cnt(p)+=k;
        if(cnt(p)>0) len(p)=uqy[r(p)+1]-uqy[l(p)];
        else len(p)=len(p*2)+len(p*2+1);
        return;
    }
    ll mid=(l(p)+r(p))>>1;
    if(l<=mid) add(p*2,l,r,k);
    if(r>mid) add(p*2+1,l,r,k);
    if(cnt(p)>0) len(p)=uqy[r(p)+1]-uqy[l(p)];
    else len(p)=len(p*2)+len(p*2+1);
//  printf("len(%lld)=%lld\n",p,len(p));
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

bool cmp(node x,node y) {
    return x.x<y.x;
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        xa=read();ya=read();xb=read();yb=read();
        a[++cnt].x=xa;a[cnt].ya=ya;a[cnt].yb=yb;a[cnt].k=1;
        a[++cnt].x=xb;a[cnt].ya=ya;a[cnt].yb=yb;a[cnt].k=-1;
        uqx[++totx]=xa;uqx[++totx]=xb;
        uqy[++toty]=ya;uqy[++toty]=yb;
    }

    sort(uqx+1,uqx+totx+1);sort(uqy+1,uqy+toty+1);
    totx=unique(uqx+1,uqx+totx+1)-uqx-1;
    toty=unique(uqy+1,uqy+toty+1)-uqy-1;

    build(1,1,toty-1);

    for(ll i=1;i<=cnt;i++) {
        a[i].x=lower_bound(uqx+1,uqx+totx+1,a[i].x)-uqx;
        a[i].ya=lower_bound(uqy+1,uqy+toty+1,a[i].ya)-uqy;
        a[i].yb=lower_bound(uqy+1,uqy+toty+1,a[i].yb)-uqy-1;
    }

    sort(a+1,a+cnt+1,cmp);

    for(ll i=1;i<=cnt;i++) {
        add(1,a[i].ya,a[i].yb,a[i].k);
        if(a[i+1].x==a[i].x) continue;
        ans+=(uqx[a[i].x+1]-uqx[a[i].x])*len(1);
    //  printf("test:len=%lld wide=%lld\n",len(1),uqx[a[i].x+1]-uqx[a[i].x]);
    }

    write(ans);

    return 0;
}