扫描线

core thinking

有一根线从 $x=0$ 到 $x=\infty$ 扫描，那所有矩形的下底到线的投影的长度是什么,矩形的下底的投影会被上边挡住

(可以理解成一个二维的括号匹配问题）

核心问题

基本思想：
正确性证明：
具体过程

在过程中是否需要知道扫描到的边是否是哪个矩形的对应边?

题目

P5490 【模板】扫描线 & 矩形面积并 - 洛谷

如何使用线段树维护区间内不为0的元素的数量

关键在于如何设计flag

全部加1 与区间信息不为0的元素数量之间的关系

手动计算，验证正确性

发现有现个面的特点：

只查询根结点，也就是说不会查询flag(标记结点)之下的结点，这导致我们不需要pushdown
上下边对应，这导致不会有一个结点的flag为负值

注意的问题2 区间离散化应该注意的问题

100 150 200 250
|
| discrete
1   2  3 4

如果需要修改 1-200 加1 在一个[1-7]的sgt上为修改 1-4,3-3
这里重要的问题3-3 这个叶子结点

解决方法: 叶子结点的代表长度不能为1，必须要代表一段长度

一个重要的性质：不会修改不是离散化后的区间范围。

下面的问题就是设计：即树上的每个点都代表一段区间，尤其是叶子结点，不存在单点的叶子

 leaf1  leaf2   leaf3
|------|-------|-------|
1     4       5        7
1     2      3        4

坐标轴上的区间分为端点值和段值

则leaf1 代表的区间是[1,4],也就是段1,2,3

| --1-- | --2-- | --3-- | --4-- | 
1       2       3       4       5

因此，我们需要找到一种方法把原区间转成对应的连续的leaf,例如

区间[4,5] 转成leaf2,leaf3
区间[1,7] 转成leaf1,leaf3,leaf3

最简单的想法，把区间的起点对应的就是右边的leaf，区间的终点对应的就是左边leaf

那么也就是，调d(i)表示点i离散化后的值，比如d(4) = 2,那么区间[l,r]对应的leaf就是d(l),d(r)-1

设 $d^{-1}(i)$ 表示i对应原来的区间端点值

TODO 图

则

leaf1 对的区间就是[d^{-1}(1),d^{-1}(1+1)]
leaf2 对的区间就是[d^{-1}(2),d^{-1}(2+1)]
leafi 对的区间就是[d^{-1}(i),d^{-1}(i+1)]

核心

不需要pushdown
区间离散化应该注意的问题
每个叶子结点代表一段区间，不存在单点的叶子
只查询根结点

TODO 使用数学证明的方式，证明 1. 不需要pushdown, 2 只查询叶子结点的情况下这种方法是正确的

证明法 1 ：递归左右式子树
本质这种操作（运算）是区间覆盖，是一种或运算，我们创造一种运算符号 $\oplus$ $father = l \oplus r$

证明无论在任何情况下，都不会让最小单位产生错误。

下面是一个无离散化的代码，用于学习入门

点击

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define maxn 500
int n;

int set_range_start;
int set_range_end;

struct _seg {
    int s,t,h;
    bool down;

    bool operator<(const _seg & other) {
        return h < other.h;
    }
};
_seg seg[5000];
int s_idx;

// ==================== sgt
struct _sgt {

    int tr[maxn*4+5];
    int flag[maxn*4+5];

    int mid(int l,int r) { return (l+r)>>1;}

    int lson(int rt) { return rt<<1;}
    int rson(int rt) { return (rt<<1)|1;}

    void build(int l,int r,int rt) {
        // TODO
    }

    void pushup(int l,int r,int rt) {
        if( flag[rt]) {
            tr[rt] = r-l+1;
        }
        else if(l == r) { //没有孩子
            tr[rt] = 0;
        } else { // 有孩子
            tr[rt] = tr[lson(rt)] +tr[rson(rt)];
        }
    }

    void update_range(int L,int R,int add,int l = set_range_start,int r = set_range_end,int rt=1) {
        if( L <= l && r <=R) {
            flag[rt] += add;
            pushup(l,r,rt);
            return ;
        }

        int m = mid(l,r);
        if( L <= m) update_range(L,R,add,l,m,lson(rt));
        if( R>=m+1) update_range(L,R,add,m+1,r,rson(rt));
        pushup(l,r,rt);
    }

    //一定查询 根
    int query(){
        return tr[1];
    }


} sgt;
// ==================== sgt end

void init(){
    cin >> n;
    int x1,y1;
    int x2,y2;

    for(int i =1;i<=n;i++){
        cin >> x1 >> y1;
        cin >> x2 >> y2;
        seg[++s_idx] = {x1,x2-1,y1,1};
        seg[++s_idx] = {x1,x2-1,y2,0};
    }

}

int main(){
    init();
    sort(seg+1,seg+1+n*2);
    ll sum = 0;
    int pre_len = 0;
    int pre_h = 0;

    //设定的sgt的区间长，
    // 这里对样例是够用的
    set_range_start = 1;
    set_range_end = 500;

    for(int i =1;i<=n*2;i++) {
        // cout << seg[i].s << " ";
        // cout << seg[i].t << " ";
        // cout << seg[i].h << " ";
        // cout << seg[i].down << " ";
        // cout <<endl;

        if( seg[i].down ) {
            sgt.update_range(seg[i].s,seg[i].t,1);
        }
        else {
            sgt.update_range(seg[i].s,seg[i].t,-1);
        }
        int len = sgt.query();
        int h = seg[i].h - pre_h;
        sum += pre_len * h;

        pre_len = len;
        pre_h = seg[i].h;

    }
    cout << sum <<endl;

    return 0;
}

下面是一个有离散化的代码

// 在1.cpp的基础上加上 离散化
//Author by [Rainboy](https://github.com/rainboylvx) 
//date: 2025-04-05 20:27:03
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef DEBUG
#define log(...)
#else
#define log(args...) { cout << "LINE:" << __LINE__ << " : ";string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}

template<typename T>
void err(istream_iterator<string> it, T a) {
cerr << *it << " = " << a << "\n";
}

template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << ", ";
err(++it, args...);
}
#endif
const int maxn = 1e6+5;
// const int range = 1e5+5;
int range =7;
int n,m;
int a[maxn];

//所有的x的元素
std::vector<int> vecx;
int diff_cnt_x; //不同的x元素的数量

//边的结构休
struct _edge {
    int s,t; //开始，结束
    int y; // 高度
    bool down; //是不是下底

    _edge() {}
    _edge(int s,int t,int y,bool down = 1): s(s),t(t),y(y),down(down) {}

    //比较大小
    bool operator<(const  _edge &b) { return y < b.y; }

};

int e_cnt;
_edge e[maxn];


//这个sgt用来求 区间内不为0的元素的个数
// 也就是区间的长度
template<typename T=int,int N=maxn>
struct sgt_range {
    T tr[N*4+5]; // 表示这段区间不为0的数量
    T flag[N*4+5]; //flag 里的内容与题目有关，灵活设定

    T left[N*4+5]; //每个节点代表的区间
    T right[N*4+5];

    // flag = x 表示这段区间全部加上x
    inline int lp(int p){return p<<1;}
    inline int rp(int p){return (p<<1)|1;}
    inline int mid(int l,int r){return (l+r)>>1;}

    inline void pushup(int l,int r,int p){  //向上合并
        if( flag[p] ) {
            // tr[p] = vecx[r-1]-vecx[l-1]+1;
            tr[p] = right[p] - left[p];
        }
        else if( l == r) { // is leaf 且为0
            tr[p] = 0;
        }
        else { // 不是leaf，也没有标记
            tr[p] = tr[lp(p)] + tr[rp(p)];
        }
    }

    void build(int l,int r,int p){ //建立
        if( l == r ) {
            //到了叶子结点
            // 更新叶子结点的代表的区间
            left[p] = vecx[l-1];
            right[p] = vecx[l];
            return;
        }
        int m = mid(l,r);
        build(l,m,lp(p));
        build(m+1,r,rp(p));
        left[p] = left[lp(p)];
        right[p] = right[rp(p)];
    }

    void debug(int l=1,int r=range,int p=1){ //建立
        cout << l <<" ";
        cout << r <<" ";
        cout << p << " ";
        cout << flag[p] << " ";
        cout << tr[p] << " ";
        cout << endl;
        if( l == r ) {
            return;
        }
        int m = mid(l,r);
        debug(l,m,lp(p));
        debug(m+1,r,rp(p));
    }

    // 区间更新
    void update(int L,int R,T v,int l,int r,int p){ 
        if(L <= l && r <= R) {
            flag[p] += v;
            pushup(l,r,p);
            return;
        }
        int m = mid(l,r);
        if( L<=m) 
            update(L,R,v,l,m,lp(p));
        if( R>=m+1)
            update(L,R,v,m+1,r,rp(p));
        pushup(l,r,p);
    }

    //区间查询
    T query(int L,int R,int l,int r,int p){
        if( L <=l && r<=R ) {
            return tr[p];
        }
        int m = mid(l,r);
        T ret = 0;
        if( L <= m ) ret+=query(L,R,l,m,lp(p));
        if( R >=m+1) ret+=query(L,R,m+1,r,rp(p));
        pushup(l,r,p);
        return ret;
    }
};
sgt_range<> sgt;


void init() {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int x1 ,y1 ,x2,y2;
        std::cin >> x1 >> y1;
        std::cin >> x2 >> y2;
        e[++e_cnt] = {x1,x2,y1,1};
        e[++e_cnt] = {x1,x2,y2,0};
        vecx.push_back(x1);
        vecx.push_back(x2); // ? 为什么要-1 ？
    }

    // 按矩形的边高度 从小到达排序
    sort(e+1,e+1+e_cnt);
}

void discrete() {
    std::sort(vecx.begin(),vecx.end());
    diff_cnt_x = std::unique(vecx.begin(),vecx.end()) - vecx.begin();
}

int _find_val_id(int val) {
    return lower_bound(vecx.begin(),vecx.begin()+diff_cnt_x,val) - vecx.begin()+1;
}


int main () {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 关闭io同步
    init();
    discrete();
    range = diff_cnt_x-1;
    sgt.build(1,range,1);
    //没有离散化,可以解20%
    int pre_h = e[1].y;
    ll pre_w = 0;
    ll sum = 0;
    for(int i =1;i<=e_cnt;i++)
    {
        const _edge &te = e[i];
        //转化区间为连续的leaf
        int L = _find_val_id(te.s);
        int R = _find_val_id(te.t)-1;
#ifdef DEBUG
        cout << te.s << " ";
        cout << te.t << " ";
        cout << te.y << " ";
        cout << te.down << " ";
        cout << endl;
        cout << "L : " << L << " ";
        cout << "R : " << R << "\n";
#endif
        if(te.down){
            // 为什么te.t-1 ?
            sgt.update(L,R,1,1,range,1);
        }
        else {
            sgt.update(L,R,-1,1,range,1);
        }

        //永远查询根节点
        ll len = sgt.query(1,range,1,range,1);
        // sum += (len * (te.y - pre_h));
        sum += pre_w * (te.y - pre_h);
#ifdef DEBUG
        cout << "len " << len ;
        cout << " add sum = " << pre_w * (te.y - pre_h);
        cout <<endl;
        sgt.debug();
        cout <<endl;
        cout <<endl;
        cout <<endl;
#endif
        pre_w = len;
        pre_h = te.y;
    }
    cout << sum << endl;
    return 0;
    
}

参考

oi-wiki scanning