扫描线

发表于 更新于 阅读次数：
扫描线算法

from OI-WIKI

题意

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

过程

现在假设我们有一根线，从下往上开始扫描：
(图片)

  1. 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
  2. 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 $1$，上面的边标记为 $-1$，每遇到一个矩形时，我们知道了标记为 $1$ 的边，我们就加进来这一条矩形的长，等到扫描到 $-1$ 时，证明这一条边需要删除，就删去，利用 $1$ 和 $-1$ 可以轻松的到这种状态。
  3. 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 $r+1$ 和 $r-1$。
  4. 需要 离散化。

附上代码及注释：

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
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000020
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
//记得加括号（（
#define int long long
#define love return
#define you 0
using namespace std;

int n;

namespace segment_tree
{
    struct node
    {
        int l, r, len, sum;
        //记录节点的左端点，右端点，此点对应的长度，以及我们需要增加总长度还是减小总长度（是矩形的靠前边否）
    }st[maxn<<3];

    struct segment
    {
        int l, r, h, vul; 
        //记录此线段的左端点右端点，高度和靠前边否
    }segg[maxn<<2];
    bool cmp(segment a, segment b) 
    {
        love a.h < b.h;
        //我们需要将边按照高度排序
    }

    int X[maxn];
    //记录线段树中需要存储的点（不相同的点）

    void pushup(int rt)
    {
        if(st[rt].sum)
        {
            st[rt].len = X[st[rt].r + 1] - X[st[rt].l];
            //当被完全覆盖的节点需要改变时改变
        }
        else
        {
            st[rt].len = st[lson].len + st[rson].len;
            //不是被完全覆盖的节点或者此节点没有贡献
        }

        love ;
    }
    void build(int rt, int l, int r)
    {
        st[rt].l = l; st[rt].r = r;
        st[rt].len = 0; st[rt].sum = 0;
        //初始化
        if(l == r) 
        {
            love ;
        } 
        build(lson, l, mid);
        build(rson, mid + 1, r);

        love ;
    }

    void update(int rt, int al_l, int al_r, int val)
    {
        int l = st[rt].l, r = st[rt].r;

        if(X[l] >= al_r || X[r + 1] <= al_l) love ;
        //剪枝
        if(X[l] >= al_l && X[r + 1] <= al_r)
        {
            st[rt].sum += val;
            //如果此节点被完全覆盖
            pushup(rt);
            //在此时就回传
            love ;
        }

        update(lson, al_l, al_r, val);
        update(rson, al_l, al_r, val);
        pushup(rt);
        //回传
        love ;
    }

    signed main()
    {
        rep(i, 1, n)
        {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            //输入
            segg[(i << 1) - 1] = (segment){x1, x2, y1, 1};
            segg[(i << 1)]     = (segment){x1, x2, y2, -1};
            //我们需要存n*2条边，这里的处理只是为了存储恰好为n*2，没有有顺序的意思
            X[(i << 1) - 1] = x1;
            X[(i << 1)] = x2;
            //存点
        }

        ll ans = 0;

        n <<= 1;
        sort(segg + 1, segg + 1 + n, cmp);
        sort(X + 1, X + n + 1);
        int cnt = unique(X + 1, X + n + 1) - X - 1;
        //去重函数，重点记忆！
        build(1, 1, cnt - 1);
        //建树

        // rep(i, 1, n) cout << segg[i].h << endl;
        // rep(i, 1, n) cout << X[i] << endl;

        rep(i, 1, n - 1)
        {
            update(1, segg[i].l, segg[i].r, segg[i].vul); 
            ans += st[1].len * (segg[i + 1].h - segg[i].h);
        }
        cout << ans << endl;
        love you;
    }
}

signed main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    cin >> n;
    segment_tree::main();

    love you;
}

一道例题 P1502

附上我也不知道怎么对的代码。。。
回头再调

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define lson (rt<<1)
#define rson (rt<<1|1)
// #define mi ((l+r)>>1)
#define maxn 300010
#define int long long
#define love return
#define you 0
int T, n, w, h, C[maxn];
// 组数，元素个数，宽，高

// namespace line_sweep
// {
    // int C[maxn<<2];
    //存横坐标
    struct segment{
        int l,r,h;
        int val;
        bool operator <(const segment &a)const{
            return (h!=a.h)?h<a.h:val>a.val;
        }
    }segg[maxn<<2];
    struct node{
        int l,r;
        int mx,add;
    }st[maxn<<2];

    void pushup(int rt)
    {
        st[rt].mx = max(st[lson].mx, st[rson].mx);    
        //上推
        love ;
    }

    void pushdown(int rt)
    {
        st[lson].mx += st[rt].add;
        st[rson].mx += st[rt].add;
        st[lson].add += st[rt].add;
        st[rson].add += st[rt].add;

        st[rt].add = 0;
        //下推
        love ;
    }

    void build(int rt, int l, int r)//建树
    {
        st[rt].l = l, st[rt].r = r;
        st[rt].add = 0; st[rt].mx = 0;
        if(l == r) love ;
        int mi = (l+r)>>1;
        build(lson, l, mi);
        build(rson, mi + 1, r);
    }
    // void build(int x,int l,int r){
    //     st[x].l=l,st[x].r=r,st[x].mx=st[x].add=0;
    //     if(l==r)return;
    //     int mi=(l+r)>>1;
    //     build(x<<1,l,mi);
    //     build(x<<1|1,mi+1,r);
    // }

    void update(int rt, int al_l, int al_r, int val)//上传
    {
        int l = st[rt].l, r = st[rt].r;
        if(l >= al_l && r <= al_r)
        {
            st[rt].mx += val;
            st[rt].add += val;
            love ;
        }
        pushdown(rt);
        
	    int mi=(l+r)>>1;
        if(al_l <= mi)update(lson, al_l, al_r, val);
        if(al_r > mi)update(rson, al_l, al_r, val);
        pushup(rt);
    }
    void init()//初始化
    {
        memset(segg, 0, sizeof(segg));
        memset(st, 0, sizeof(st));
    }

    // signed main()
    // {
    //     init();
    //     rep(i, 1, n)
    //     {
    //         int x, y, v; cin >> x >> y >> v;
    //         C[(i << 1) - 1] = y; 
    //         C[(i << 1)] = y + h - 1;
    //         segg[(i << 1) - 1] = (segment){y, y + h - 1, x, v};
    //         segg[(i << 1)] = (segment){y, y + h - 1, x + w - 1, -v};
    //     }

    //     n <<= 1;

    //     sort(segg + 1, segg + n + 1);
    //     sort(X + 1, X + n + 1);
    //     int cnt = unique(X + 1, X + n + 1) - (X + 1);

    //     rep(i, 1, n)
    //     {
    //         int pos1 = lower_bound(X + 1, X + cnt + 1, segg[i].l) - X;
    //         int pos2 = lower_bound(X + 1, X + cnt + 1, segg[i].r) - X;
    //         segg[i].r = pos2; 
    //         segg[i].l = pos1;
    //     }

    //     build(1, 1, cnt);

    //     int ans = 0;

    //     rep(i, 1, n)
    //     {
    //         update(1, segg[i].l, segg[i].r, segg[i].val);
    //         ans = max(ans, st[1].mx);
    //     }

    //     cout << ans << endl;

        // love you;
    // }
// }

signed main()
{
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    // cin >> T;
    // while(T --)
    // {
// 3 5 4
// 1 2 3
// 2 3 2
// 6 3 1
        cin >> n >> w >> h;
        // init();
        rep(i, 1, n)
        {
            int x, y, v; cin >> x >> y >> v;
            C[(i << 1) - 1] = y; 
            C[(i << 1)] = y + h - 1;
            segg[(i << 1) - 1] = (segment){y, y + h - 1, x, v};
            segg[(i << 1)] = (segment){y, y + h - 1, x + w - 1, -v};
        }

        n <<= 1;

        sort(segg + 1, segg + n + 1);
        sort(C + 1, C + n + 1);
        int cnt = unique(C + 1, C + n + 1) - (C + 1);

        rep(i, 1, n)
        {
            int pos1 = lower_bound(C + 1, C + cnt + 1, segg[i].l) - C;
            int pos2 = lower_bound(C + 1, C + cnt + 1, segg[i].r) - C;
            segg[i].r = pos2; 
            segg[i].l = pos1;
        }

        build(1, 1, cnt);

        int ans = 0;

        rep(i, 1, n)
        {
            update(1, segg[i].l, segg[i].r, segg[i].val);
            ans = max(ans, st[1].mx);
        }

        cout << ans << endl;
        // line_sweep::main();
    // }

    love you;
}