跳转至

扫描线

有些题目可以直接使用数据结构解决；但有时还有额外的一维约束条件需要被满足，这时候就可以考虑离线、排序，使用扫描线压掉这一维；剩下的子问题就可以使用数据结构求解了。

更多扫描线的用法请参见二维数点、cdq分治。

例题

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

题目大意

给定 \(n\) 个矩形，求其并集的面积。

我们将每个矩形 \((x_1,y_1,x_2,y_2)\) 都拆分成两条带权的线段：\((x_1,y_1,y_2,1)\) 和 \((x_2,y_1,y_2,-1)\)。那么问题本质就是求每个 \(x\) 处，位于其左边的所有线段的并集的总长度是多少。这实际上是 \(1\) 维的约束，但重合部分的处理需要使用数据结构，因此需要使用扫描线把 \(x\) 维度压掉。

先离线处理出所有线段，按 \(x\) 排序；接着依次遍历每条线段：

  • 在线段树中查询 \(>0\) 的值的个数 \(num\)，它们对答案有 \(num\times(line[i].x-line[i-1].x)\) 的贡献；
  • 在线段树中对 \([y_1,y_2]\) 进行区间 \(+1\) 或区间 \(-1\)。

如何使用线段树求出 \(>0\) 的值有多少个呢？我们用线段树同时维护区间最小值和区间最小值出现的次数。如果区间最小值等于 \(0\)，那么最小值出现的次数就是 \(0\) 出现的次数。用区间长度减去 \(0\) 出现过的次数即可。

注意事项：

  • 由于题目中提供的是每个矩形四个顶点的几何坐标。若要转化为可以用线段树维护的网格坐标，需要将闭区间 \([y_1,y_2]\) 转换为右半开区间 \([y_1,y_2)\)

几何坐标示意图 网格坐标示意图

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include<iostream>
#include<algorithm>
#define int long long
#define cint const int&
using namespace std;
const int N = 1E5 + 10;
const int LOGN = 35;
const int A = 1E9 + 10;

struct myPair {
    int x, y1, y2, val;
    inline bool operator<(const myPair& other) const {
        return x < other.x;
    }
} line[2 * N];

int nn;
struct Node {
    int lc, rc, tag;
    int Min, mCnt;
} tree[2 * N * LOGN];

int n, ans;

int addNode(cint l, cint r) {
    tree[++nn] = {0, 0, 0, 0, r - l + 1};
    return nn;
}

void move_tag(cint p, cint tg) {
    tree[p].tag += tg;
    tree[p].Min += tg;
}

void push_up(cint p) {
    int lc = tree[p].lc, rc = tree[p].rc;
    tree[p].mCnt = 0;
    tree[p].Min = min(tree[lc].Min, tree[rc].Min);
    if(tree[p].Min == tree[lc].Min) tree[p].mCnt += tree[lc].mCnt;
    if(tree[p].Min == tree[rc].Min) tree[p].mCnt += tree[rc].mCnt;
}

void push_down(cint p, cint l, cint r, cint mid) {
    if(tree[p].lc == 0) tree[p].lc = addNode(l, mid);
    if(tree[p].rc == 0) tree[p].rc = addNode(mid + 1, r);
    if(tree[p].tag) {
        int lc = tree[p].lc, rc = tree[p].rc;
        move_tag(lc, tree[p].tag);
        move_tag(rc, tree[p].tag);
        tree[p].tag = 0;
    }
}

void modify(int p, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {
        tree[p].tag += v;
        tree[p].Min += v;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(p, l, r, mid);
    if(mid >= ql) {
        int lc = tree[p].lc;
        modify(lc, l, mid, ql, qr, v);
    }
    if(mid < qr) {
        int rc = tree[p].rc;
        modify(rc, mid + 1, r, ql, qr, v);
    }
    push_up(p);
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    addNode(0, A - 1);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        line[2 * i - 1] = {x1, y1, y2, 1};
        line[2 * i] = {x2, y1, y2, -1};
    }

    sort(line + 1, line + 1 + 2 * n);

    for(int i = 1; i <= 2 * n; i++) {
        myPair &cur = line[i];
        if(cur.val == 1) {
            ans += (cur.x - line[i - 1].x) * (A - tree[1].mCnt);
            modify(1, 0, A - 1, cur.y1, cur.y2 - 1, 1);
        } else {
            ans += (cur.x - line[i - 1].x) * (A - tree[1].mCnt);
            modify(1, 0, A - 1, cur.y1, cur.y2 - 1, -1);
        }
    }

    cout << ans << endl;

    return 0;
}

P1856 [IOI1998] [USACO5.5] 矩形周长Picture

题目大意

给定 \(n\) 个矩形，求其并集的周长。

图片

考虑改进矩形面积并的思路。观察样例不难发现，可以先统计所有横向的边的贡献，再统计所有竖向的边的贡献。

我们先考虑处理竖向边的贡献（横向边同理）。我们注意到：

  • 有一条权值为 \(+1\) 的边 \((x_i,y_{i,1},y_{i,2})\)，设区间 \([y_{i,1},y_{i,2}]\) 有 \(k\) 个位置为 \(0\)，则这条边就会产生 \(k\) 的贡献。
  • 有一条边权为 \(-1\) 的边 \((x_i,y_{i,1},y_{i,2})\)，则先给区间 \([y_{i,1},y_{i,2}]\) 减 \(1\)，再统计此区间内 \(0\) 的数量，记为 \(k\)，则这条边就会产生 \(k\) 的贡献。

本题用普通线段树维护即可。时间复杂度 \(O(n\log n)\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<algorithm>
#include<utility>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1E4 + 10;
const int LOGN = 18;
const int INF = 0x3f3f3f3f3f3f3f3f;

inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }

struct Rec {
    int x1, y1, x2, y2;
} a[N];

struct Edge {
    int x, y1, y2, val;
    inline bool operator<(const Edge &other) const {
        if(x != other.x) return x < other.x;
        return val > other.val;
    }
} q[2 * N];

int n, ans;
int Min[8 * N], mcnt[8 * N], tag[8 * N];

pii merge(const pii &a, const pii &b) {
    pii res = {min(a.first, b.first), 0};
    if(res.first == a.first) res.second += a.second;
    if(res.first == b.first) res.second += b.second;
    return res;
}

void push_up(int p) {
    Min[p] = min(Min[lc(p)], Min[rc(p)]);
    mcnt[p] = 0;
    if(Min[p] == Min[lc(p)]) mcnt[p] += mcnt[lc(p)];
    if(Min[p] == Min[rc(p)]) mcnt[p] += mcnt[rc(p)];
}

void move_tag(int p, int tg) {
    Min[p] += tg;
    tag[p] += tg;
}

void push_down(int p) {
    if(tag[p]) {
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }
}

void build_tree(int p, int l, int r) {
    tag[p] = Min[p] = mcnt[p] = 0;
    if(l == r) {
        Min[p] = 0;
        mcnt[p] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(lc(p), l, mid);
    build_tree(rc(p), mid + 1, r);
    push_up(p);
}

void modify(int p, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {
        move_tag(p, v);
        return;
    }
    int mid = (l + r) >> 1;
    push_down(p);
    if(mid >= ql) modify(lc(p), l, mid, ql, qr, v);
    if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    push_up(p);
}

pii query(int p, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) {
        return {Min[p], mcnt[p]};
    }
    int mid = (l + r) >> 1;
    push_down(p);
    if(mid >= qr) return query(lc(p), l, mid, ql, qr);
    if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
    return merge(query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr));
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    build_tree(1, 1, 2 * N);
    for(int i = 1; i <= n; i++) {
        int x1 = a[i].x1, y1 = a[i].y1, x2 = a[i].x2, y2 = a[i].y2 - 1;
        q[i * 2 - 1] = {x1, y1, y2, 1};
        q[i * 2] = {x2, y1, y2, -1};
    }
    sort(q + 1, q + 1 + 2 * n);
    for(int i = 1; i <= 2 * n; i++) {
        Edge &cur = q[i];
        if(cur.val == 1) {
            pii res = query(1, 1, 2 * N, cur.y1 + N, cur.y2 + N);
            ans += (res.first == 0) ? res.second : 0;
            modify(1, 1, 2 * N, cur.y1 + N, cur.y2 + N, 1);
        } else {
            modify(1, 1, 2 * N, cur.y1 + N, cur.y2 + N, -1);
            pii res = query(1, 1, 2 * N, cur.y1 + N, cur.y2 + N);
            ans += (res.first == 0) ? res.second : 0;
        }
    }

    build_tree(1, 1, 2 * N);
    for(int i = 1; i <= n; i++) {
        int x1 = a[i].x1, y1 = a[i].y1, x2 = a[i].x2 - 1, y2 = a[i].y2;
        q[i * 2 - 1] = {y1, x1, x2, 1};
        q[i * 2] = {y2, x1, x2, -1};
    }
    sort(q + 1, q + 1 + 2 * n);
    for(int i = 1; i <= 2 * n; i++) {
        Edge &cur = q[i];
        if(cur.val == 1) {
            pii res = query(1, 1, 2 * N, cur.y1 + N, cur.y2 + N);
            ans += (res.first == 0) ? res.second : 0;
            modify(1, 1, 2 * N, cur.y1 + N, cur.y2 + N, 1);
        } else {
            modify(1, 1, 2 * N, cur.y1 + N, cur.y2 + N, -1);
            pii res = query(1, 1, 2 * N, cur.y1 + N, cur.y2 + N);
            ans += (res.first == 0) ? res.second : 0;
        }
    }

    cout << ans << endl;

    return 0;
}