P5490 【模板】扫描线与矩形面积并

矩形面积并：扫描线维护纵向覆盖长度

问题

P5490 【模板】扫描线 & 矩形面积并
求若干个边平行于坐标轴的矩形所覆盖的总面积。

数据规模：$n\le 10^5$，坐标不超过 $10^9$。

这是一道扫描线的模板，不过我觉得扫描线严格来说不是一个算法，而是一个思想，或者说是做题的技巧。

顾名思义，扫描线就是一条很长的线，将序列离散化之后，发现产生变化的位置不会特别多，所以用这根线处理产生变化的地方，然后处理变化，统计贡献就可以解决问题了。

注：有一个常见的误区，扫描线不一定要和复杂的数据结构一起使用，用简单的数据结构也能处理好变化。

比如说下面这个一维的问题：

显然有一个线段树的 $\mathcal{O}(N \log( N))$ 的做法；当然我们也可以用扫描线来做：发现产生变化的位置就是每条线段的左右端点，于是我们把这些位置都切开，如下：

发现一个性质：相邻的两个事件坐标之间不会再发生覆盖状态变化，因此这一整段的覆盖次数保持不变。

于是可以给每条线段的左端点打上 $+1$ 标记，右端点打上 $-1$ 标记。按坐标扫描并维护标记前缀和：覆盖次数大于 $0$ 的小段被覆盖，等于 $0$ 的小段未被覆盖；多条线段重叠时也能自然处理。

---

说完了一维的简单情况，我们回到本题二维问题上，难点在于处理多个矩形重叠的部分。而这种不规则的图形，我们常用的方法就是割补法。

所以我们刚刚发现的性质，每相邻的两个事件线中间可能有多个矩形，但他们的宽度都是一样的（ $x$ 轴 ），那么问题就变成了底边长度如何处理？

然后我们就把二维的问题转化到了底边长度这一一维问题上，由于每次进入或者离开都是修改某一段区间，所以我们可以采用线段树来维护。

由于这是个区间覆盖模型，所以我们不需要懒标记，直接维护区间表示的长度 len，有无被完全覆盖 cnt，以及长度总和 sum 即可。

示例

注：线段树中的节点是左闭右开的，这样可以完整表示连续段，比如说叶子 $i$ 表示 $[disc[i], disc[i+1])$，长度就是 $disc[i+1] - disc[i]$。同理更新时用 $[l, r-1]$ 也是因为节点左闭右开。

▶

P5490

struct Disc {
/* ======================================== */
vector<int> v;
void clear( ) { v.clear( ); }
void add( int x ) { v.push_back( x ); }
void init( ) {
    sort( v.begin( ), v.end( ) );
    v.erase( unique( v.begin( ), v.end( ) ), v.end( ) );
}
int size( ) { return v.size( ); }
int get_idx( int x ) { return lower_bound( v.begin( ), v.end( ), x ) - v.begin( ) + 1; }
int get_val( int idx ) { return v[idx - 1]; }
/* ======================================== */
} disc;

#define ls ( u << 1 )
#define rs ( u << 1 | 1 )

struct SegTree {
/* ======================================== */
struct Node { 
    int l, r;
    ll cnt, sum;
} tr[maxn << 2];

ll len( int u ) {
    return 1ll * disc.get_val( tr[u].r + 1 ) - disc.get_val( tr[u].l );
}

void push_up( int u ) {
    if( tr[u].cnt ) tr[u].sum = len( u );
    else if( tr[u].l == tr[u].r ) tr[u].sum = 0;
    else tr[u].sum = tr[ls].sum + tr[rs].sum;
}

void build( int u, int l, int r ) {
    tr[u] = {l, r, 0, 0};
    if( l == r ) return ;
    int mid = ( l + r ) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
}

void upd( int u, int l, int r, int val ) {
    if( l <= tr[u].l && tr[u].r <= r ) { 
        tr[u].cnt += val;
        push_up( u );
        return ;
    }
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r, val );
    if( mid < r ) upd( rs, l, r, val );
    push_up( u );
}
ll ask( ) { return tr[1].sum; }
/* ======================================== */
} seg;

struct Event {
    ll x, y1, y2;
    int tag;
    bool operator < ( const Event &oth ) const { return x < oth.x; }
};
vector<Event> events;

void solve( ) {
    int n = read( );
    
    disc.clear( );
    events.clear( );
    events.reserve( n << 1 );

    for( int i = 1; i <= n; ++ i ) {
        int x1 = read( ), y1 = read( ), x2 = read( ), y2 = read( );
        events.push_back({ x1, y1, y2, 1 });
        events.push_back({ x2, y1, y2, -1 });
        disc.add( y1 );
        disc.add( y2 );
    }
    
    disc.init( );
    sort( events.begin( ), events.end( ) );

    ll ans = 0;
    int m = disc.size( );
    seg.build( 1, 1, m - 1 );

    int ecnt = events.size( );
    for( int i = 0; i < ecnt - 1; ++ i ) {
        auto [x, y1, y2, opt] = events[i];
        int l = disc.get_idx( y1 );
        int r = disc.get_idx( y2 );
        seg.upd( 1, l, r - 1, opt );
        ans += seg.ask( ) * ( events[i + 1].x - x );
    }
    cout << ans << '\n';
}

记录

• 归属：[[扫描线模型|扫描线]]、计算几何/矩形面积并

• 新增：线段树维护的是离散坐标之间的实际线段，并通过“整段覆盖计数 + 子区间覆盖长度”处理重叠区间的长度并。

• 分类：待定