「LeetCode」线段树 - Segment Tree

2020-05-22
摘要: 本文介绍了线段树及其应用(扫描线)。

线段树 - Segment Tree#

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树可以在 $\log(N)$ 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。

线段树维护的信息,需要满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用懒惰标记时,标记也要满足可加性(例如取模就不满足可加性,对 $4$ 取模然后对 $3$ 取模,两个操作就不能合并在一起做)。

基本结构#

线段树将每个长度不为 $1$ 的区间划分成左右两个区间递归求解,把整个线段划分为一个树形结构,通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

有个大小为 $5$ 的数组 $a={10,11,12,13,14}$ ,要将其转化为线段树,有以下做法:设线段树的根节点编号为 $1$ ,用数组 $d$ 来保存我们的线段树, $d_i$ 用来保存线段树上编号为 $i$ 的节点的值(这里每个节点所维护的值就是这个节点所表示的区间总和),如图所示:

图中 $d_1$ 表示根节点,如 $d_1$ 所表示的区间就是 $[1,5]$ ( $a_1,a_2, \cdots ,a_5$ ),即 $d_1$ 所保存的值是 $a_1+a_2+ \cdots +a_5$ , $d_1=60$ 表示的是 $a_1+a_2+ \cdots +a_5=60$ 。

建树#

这里推荐一个非常优秀的介绍视频: 线段树(Segment Tree)

我们采用左右递归的思路来建树:先后建立当前结点的左、右子树,再根据其值建立当前结点。我们只需要给出递归的出口(叶子结点)即可。

void build_tree(vector<int>& arr, vector<int>& tree, int node, int start, int end) {
    // suppose that indices are from 1 to n. range: [start, end]
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    
    int mid = (end - start)/2 + start; // prevent overflow
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    build_tree(arr, tree, left_node, start, mid);
    build_tree(arr, tree, right_node, mid+1, end);
    tree[node] = tree[left_node] + tree[right_node];
}

空间大小#

关于线段树的空间:如果采用堆式存储( $2p$ 是 $p$ 的左儿子, $2p+1$ 是 $p$ 的右儿子),若有 $n$ 个叶子结点,则 $d$ 数组的范围最大为 $2^{\left\lceil\log{n}\right\rceil+1}$ 。

分析:容易知道线段树的深度是 $\left\lceil\log{n}\right\rceil$ 的,则在堆式储存情况下叶子节点(包括无用的叶子节点)数量为 $2^{\left\lceil\log{n}\right\rceil}$ 个,又由于其为一棵完全二叉树,则其总节点个数 $2^{\left\lceil\log{n}\right\rceil+1}-1$ 。当然如果你懒得计算的话可以直接把数组长度设为 $4n$ ,因为 $\frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n}$ 的最大值在 $n=2^{x}+1(x\in N_{+})$ 时取到,此时节点数为 $2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5$ 。

区间查询#

同样地,我们采用递归的方法。只需要合并左右两颗子树的查询结果即可。注意我们通过判断查询区间 $A:[L,R]$ 与当前结点的区间 $B:[\mathrm{start},\mathrm{end}]$ 的关系来决定是否跳出递归。具体地来说,若两个区间没有交集,则返回 $0$;若 $B\subseteq A$,则直接返回结点的值,无需向下递归;否则都应该将区间拆开,向下递归。

int query_tree(vector<int>& tree, int node, int start, int end, int L, int R) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R].
    if(R < start || L > end) {
        return 0;
    } else if (L <= start && end <= R) {
        return tree[node];
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    int sum_left  = query_tree(tree, left_node, start, mid, L, R);
    int sum_right = query_tree(tree, right_node, mid+1, end, L, R);
    
    return sum_left + sum_right;
}

单点修改#

同样地,我们采用递归的方法。只需要先后修改左右两颗子树,再根据其新值更新当前结点即可。注意我们通过判断 $\mathrm{idx}$ 与当前结点左右子树的区间 $\mathrm{left:} [\mathrm{start},\mathrm{mid}], \mathrm{right:} [\mathrm{mid}+1, \mathrm{end}]$ 的关系来决定更新哪颗子树。当 $\mathrm{start}==\mathrm{end}$ 时跳出递归。

void update_tree(vector<int>& arr, vector<int>& tree, int node, int start, int end, int idx, int val) {
    // suppose that indices are from 1 to n. range: [start, end]
    // !!! arr[idx] = val
    if (start == end) {
        arr[idx] = val;
        tree[node] = val;
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    if(idx >= start && idx <= mid) {
        update_tree(arr, tree, left_node, start, mid, idx, val);
    } else {
        update_tree(arr, tree, right_node, mid+1, end, idx, val);
    }
    tree[node] = tree[left_node] + tree[right_node];
}

区间修改(Lazy 标记)#

如果要求修改区间 $[L,R]$ ,把所有包含在区间 $[L,R]$ 中的节点都遍历一次、修改一次,时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。

我们设一个数组 $b$ , $b_i$ 表示编号为 $i$ 的节点的懒惰标记值。为了加强对懒惰标记的理解,此处举个例子:

我们把区间 $[1,3]$ 的值都增加 $2$,但是我们只需要令 b[2] += 2d[2] += 2*(3-1+1)。这样当我们只查询 $[1, 3]$ 的时候是没有问题的,但是如果要查询它的子区间,比如 $[1,2]$,就会出现问题。所以我们需要下传懒惰标记。如图所示:

所以我们每次查询时,如果发现有懒惰标记,则下传其懒惰标记再继续查询。

void update_tree(vector<int>& tree, vector<int>& lazy, int node, int start, int end, int L, int R, int val) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    // !!! a[i] += val, i in [L, R]
    if (R < start || L > end) {
        return;
    } else if (L <= start && end <= R) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    // 清除当前结点的 lazy 标记
    if(lazy[node] && start!= end) {
        tree[left_node] += lazy[node] * (mid - start + 1);
        lazy[left_node] += lazy[node];
        tree[right_node] += lazy[node] * (end - mid);
        lazy[right_node] += lazy[node];
        lazy[node] = 0;
    }
    
    update_tree(tree, lazy, left_node, start, mid, L, R, val);
    update_tree(tree, lazy, right_node, mid+1, end, L, R, val);
    tree[node] = tree[left_node] + tree[right_node];
}


int query_tree(vector<int>& tree, vector<int>& lazy, int node, int start, int end, int L, int R) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    if(R < start || L > end) {
        return 0;
    } else if (L <= start && end <= R) {
        return tree[node];
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    // 清除当前结点的 lazy 标记
    if(lazy[node]) {
        tree[left_node] += lazy[node] * (mid - start + 1);
        lazy[left_node] += lazy[node];
        tree[right_node] += lazy[node] * (end - mid);
        lazy[right_node] += lazy[node];
        lazy[node] = 0;
    }
    
    int sum_left = query_tree(tree, lazy, left_node, start, mid, L, R);
    int sum_right = query_tree(tree, lazy, right_node, mid+1, end, L, R);
    
    return sum_left + sum_right;
}

其他应用#

扫描线问题#

线段树也可以用来处理扫描线问题。扫描线一般运用在图形上面,它和它的字面意思十分相似,就是一条线在整个图上扫来扫去,它一般被用来解决图形面积,周长等问题。

例题#

luogu P3372【模板】线段树 1#

luogu P3372【模板】线段树 1

#pragma clang optimize on
#pragma GCC optimize(2)

#include <iostream>
#include <vector>

using namespace std;

void build_tree(vector<long long>& arr, vector<long long>& tree, int node, int start, int end) {
    // suppose that indices are from 1 to n. range: [start, end]
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    
    int mid = (end - start)/2 + start; // prevent overflow
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    build_tree(arr, tree, left_node, start, mid);
    build_tree(arr, tree, right_node, mid+1, end);
    tree[node] = tree[left_node] + tree[right_node];
}

void update_tree(vector<long long>& tree, vector<long long>& lazy, int node, int start, int end, int L, int R, int val) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    // !!! a[i] += val, i in [L, R]
    if (R < start || L > end) {
        return;
    } else if (L <= start && end <= R) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    // 清除当前结点的 lazy 标记
    if(lazy[node]) {
        tree[left_node] += lazy[node] * (mid - start + 1);
        lazy[left_node] += lazy[node];
        tree[right_node] += lazy[node] * (end - mid);
        lazy[right_node] += lazy[node];
        lazy[node] = 0;
    }
    
    update_tree(tree, lazy, left_node, start, mid, L, R, val);
    update_tree(tree, lazy, right_node, mid+1, end, L, R, val);
    tree[node] = tree[left_node] + tree[right_node];
}

long long query_tree(vector<long long>& tree, vector<long long>& lazy, int node, int start, int end, int L, int R) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    if(R < start || L > end) {
        return 0;
    } else if (L <= start && end <= R) {
        return tree[node];
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    // 清除当前结点的 lazy 标记
    if(lazy[node]) {
        tree[left_node] += lazy[node] * (mid - start + 1);
        lazy[left_node] += lazy[node];
        tree[right_node] += lazy[node] * (end - mid);
        lazy[right_node] += lazy[node];
        lazy[node] = 0;
    }
    
    long long sum_left = query_tree(tree, lazy, left_node, start, mid, L, R);
    long long sum_right = query_tree(tree, lazy, right_node, mid+1, end, L, R);
    
    return sum_left + sum_right;
}

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<long long> arr(n+1, 0), tree(4*n, 0), lazy(4*n, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    build_tree(arr, tree, 1, 1, n);
    
    int type, x, y, k;
    for(int i = 0; i < m; ++i) {
        cin >> type;
        if (type == 1) {
            cin >> x >> y >> k;
            update_tree(tree, lazy, 1, 1, n, x, y, k);
        } else {
            cin >> x >> y;
            cout << query_tree(tree, lazy, 1, 1, n, x, y) << endl;
        }
    }
}

POJ 2528 Mayor’s posters#

POJ 2528 Mayor’s posters

我们只需要倒着考虑贴海报的次序,因为后贴的具有优先权。在倒着考虑的过程中,只需要查找当前海报的区间 $[L,R]$ 是否已经被完全覆盖了,如果未被完全覆盖,那么就可以贴上,并且更新区间覆盖的信息,否则无法贴上。我们借助线段树去维护区间的信息,我们只需要给区间做标记即可,我们不需要 Lazy 数组(因为不需要对区间求和,而是只查询区间是否被标记)。对于 update 来说,我们只需要去更新对应区间的标记,如果发现其中某一段区间之前已经被覆盖了,直接 return 即可;对于 query 来说(返回值为 true 代表区间已全覆盖),我们只需要保证左右子树都全覆盖,即返回 true。

注意这题还需要用到离散化,而且有一个小问题必须解决(虽然不解决 POJ 也能过…)。

另外注意区间的总范围应该是离散化后的范围($N$)。

#pragma clang optimize on
#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void update_tree(vector<bool>& coverd, int node, int start, int end, int L, int R) {
    // suppose that indices are from 1 to N. range: [start, end], [L, R]
    if (R < start || L > end) {
        return;
    } else if (L <= start && end <= R) {
        coverd[node] = true;
        return;
    }
    
    if(coverd[node]) {
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    update_tree(coverd, left_node, start, mid, L, R);
    update_tree(coverd, right_node, mid+1, end, L, R);
    coverd[node] = coverd[left_node] && coverd[right_node];
}

bool query_tree(vector<bool>& coverd, int node, int start, int end, int L, int R) {
    // suppose that indices are from 1 to N. range: [start, end], [L, R]
    if(R < start || L > end) {
        return true;
    } else if (L <= start && end <= R) {
        return coverd[node];
    }
    
    if(coverd[node]) {
        return true;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    bool query_left = query_tree(coverd, left_node, start, mid, L, R);
    bool query_right = query_tree(coverd, right_node, mid+1, end, L, R);
    
    return query_left && query_right;
}

int main() {
    ios::sync_with_stdio(false);
    int count;
    cin >> count;
    while(count--) {
        int n;
        cin >> n;
        vector<pair<int, int> > interval(n);
        vector<int> seg(2*n);
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            cin >> interval[i].first >> interval[i].second;
            
            // 把区间改成 [L, R) 再离散化,防止 [1, 5], [1,2], [4, 5] 离散化后吃掉了 3
            interval[i].second++;
            
            seg[cnt++] = interval[i].first;
            seg[cnt++] = interval[i].second;
        }
        
        sort(seg.begin(), seg.begin()+cnt);
        vector<int>::iterator end = unique(seg.begin(), seg.begin()+cnt);
        int N = int(end - seg.begin());
        
        vector<bool> coverd(4*N, false);
        int ans = 0;
        for(int i = n-1; i >= 0; --i) {
            interval[i].first = int(lower_bound(seg.begin(), end, interval[i].first) - seg.begin()) + 1;
            interval[i].second = int(lower_bound(seg.begin(), end, interval[i].second) - seg.begin()) + 1 - 1;
            if (!query_tree(coverd, 1, 1, N, interval[i].first, interval[i].second)) {
                ans++;
                update_tree(coverd, 1, 1, N, interval[i].first, interval[i].second);
            }
        }
        cout << ans << endl;
    }
}

扫描线 POJ 1151 Atlantis#

扫描线 POJ 1151 Atlantis

这是一个经典的扫描线问题,如图所示(以从下至上为例):

我们可以选择从下至上/从上至下/从左至右/从右至左进行扫描,每碰到一根线就统计和前一根线之间的面积。于是我们需要解决两个问题:怎么统计覆盖区间的长度怎么计算宽度

覆盖区间长度#

经过观察我们发现,如果我们碰到矩形的入边,入边所在的区间 $[L_1, R_1]$ 就应该被覆盖。我们如果用 Cover 数据表示其被覆盖的次数(可能不同矩形之间会多次重复覆盖,如图橙色部分),就对应着 $\mathrm{Cover}[i] = \mathrm{Cover}[i]+1, i\in[L_1,R_1]$。如果碰到矩形的出边,出边所在的区间 $[L_2, R_2]$ 就应该取消一层覆盖,也就是 $\mathrm{Cover}[i] = \mathrm{Cover}[i]-1, i\in[L_2,R_2]$。因此任意时刻统计的覆盖区间的长度就是 Cover 值为正的点的个数。既然如此,区间修改的操作我们就可以采用线段树来实现。

但是怎么维护区间覆盖的长度?我们需要时刻知道到底有几个点的 Cover 值为正,普通的线段树达不到这个效果。我们需要修改一下线段树维护的信息。对于每个结点来说,它维护着 Cover 值和 Len 值,Cover 值代表着当前区间是否被直接覆盖(某个矩形的入边直接覆盖了它)。注意(或者不注意也没关系),这句话意味着,就算 Cover 值为 $0$,该区间也可能被完全覆盖,只是不是由单个矩形覆盖的(此时左右两个子结点应被完全覆盖)。Len 值代表当前区间范围中,被覆盖的区间长度。

// 更新长度信息
if(cover[node])
    // 映射回真实的长度
    len[node] = y[end-1] - y[start-1];
else
    len[node] = len[node * 2] + len[node * 2 + 1];

我们给出上述代码来根据 Cover 值来更新 Len 值。如果当前区间被直接覆盖,那么当前的区间 Len 值就是区间的真实长度(从离散化后的值映射回真实的 $y$)。如果没有直接覆盖,那么当前区间的 Len 值应该是左右区间的 Len 值之和。于是我们只需要在每次更新 Cover 后,或者更新子结点的 Len 后更新当前结点的 Len 即可,这样 len[1] 始终就是覆盖区间的长度。

宽度#

因为我们要按坐标轴来遍历所有线,所以应该对所有线进行排序,那么相邻线就是相邻元素,可以直接求出线之间的距离,也就是宽度。

离散化#

某些题目可能数据比较大,因此需要先离散化。但是注意,我们需要时刻维护区间的长度,离散化之后区间的点坐标发生了变化,因此在计算区间长度的时候应该映射回去(下标查询即可完成)。

线段树的修改#

我们发现一个问题,对于普通的线段树:

如果我们要执行求 $[1,4]$ 中区间覆盖的长度,我们无法找到 $[3,4]$ 这个区间是否被覆盖的信息。因为原本的线段树存储的是的信息,而我们现在需要区间的信息。因此叶子结点应该是诸如 $[1,2]$ 的长度为 $1$ 的区间。如图所示:

这样我们就可以对每一段区间进行查询。注意写代码的时候修改递归部分对应的区间下标。然后数组开 $4$ 倍会不够,开 $8$ 倍就够了..

代码#
#pragma clang optimize on
#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

void update_tree(vector<int>& cover, vector<double>& len,vector<double>& y, int node, int start, int end, int L, int R, int val) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    // !!! a[i] += val, i in [L, R]
    if (R < start || L > end) {
        return;
    } else if (L <= start && end <= R) {
        cover[node] += val;
        
        // 更新长度信息
        if(cover[node])
            // 映射回真实的长度
            len[node] = y[end-1] - y[start-1];
        else
            len[node] = len[node * 2] + len[node * 2 + 1];
        return;
    } else if (end - start == 1) {
        // 区间长度为 1 就返回
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    update_tree(cover, len, y, left_node, start, mid, L, R, val);
    update_tree(cover, len, y, right_node, mid, end, L, R, val); // !! "mid" instead of "mid+1".
    
    // 更新长度信息
    if(cover[node])
        // 映射回真实的长度
        len[node] = y[end-1] - y[start-1];
    else
        len[node] = len[node * 2] + len[node * 2 + 1];
}

struct Line {
    int type; // 1 represents in-bound, -1 represents out-bound
    double x;
    double y1, y2;
    bool operator <(const Line& rhs) const{
        return x < rhs.x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, index = 1;
    while(cin >> n) {
        if(n == 0) break;
        vector<Line> lines(2*n+1);
        vector<double> y; // 用于离散化的数组
        y.reserve(2*n+1);
        int p = 1;
        for(int i = 1; i <= n; ++i) {
            double a, b, c, d;
            cin >> a >> b >> c >> d;
            
            lines[p].type = 1;
            lines[p].x = a;
            lines[p].y1 = b;
            lines[p++].y2 = d;
            lines[p].type = -1;
            lines[p].x = c;
            lines[p].y1 = b;
            lines[p++].y2 = d;
            y.push_back(b);
            y.push_back(d);
        }
        
        sort(lines.begin(), lines.end());
        sort(y.begin(), y.end());
        vector<double>::iterator end = unique(y.begin(), y.end());
        int N = int(end - y.begin());
        
        vector<int> cover(8*N+1, 0);
        vector<double> len(8*N+1, 0);
        double ans = 0;
        for(int i = 1; i <= 2*n; ++i) {
            lines[i].y1 = int(lower_bound(y.begin(), end, lines[i].y1) - y.begin() + 1);
            lines[i].y2 = int(lower_bound(y.begin(), end, lines[i].y2) - y.begin() + 1);
//            cout << len[1] << "*" << (lines[i].x-lines[i-1].x) << "=" << len[1]*(lines[i].x-lines[i-1].x) << endl;
            ans += len[1]*(lines[i].x-lines[i-1].x);
            update_tree(cover, len, y, 1, 1, N, int(lines[i].y1), int(lines[i].y2), lines[i].type);
        }
        cout << "Test case #" << index++ << endl;
        printf("Total explored area: %.2f\n\n", ans);
    }
    
    return 0;
}

扫描线 HDOJ 1828 Picture#

扫描线 HDOJ 1828 Picture

这题也是扫描线的应用,只不过求的是周长而不是面积:

同样地我们可以从四个方向进行扫描。我们只需要定义如何计算周长即可。

方法一#

我们只要能够算出一个方向的的周长(比如平行于 $x$ 轴),类比就可以求出另一个方向。对于平行于 $x$ 轴的线来说,我们有一个结论:每次遇到扫描线就执行 ans += abs(Len - LastLen),因为出矩形时计算结果为负数,因此要加上绝对值,其中 Len 是当前更新后的覆盖区间长度,LastLen 是上次更新后的覆盖区间长度。Len 数组的维护方式在上一题计算面积中已经给出。

方法二#

我们想办法一次性计算出所有方向的周长。在计算平行于 $x$ 轴的周长时,我们同时计算竖直方向的周长。但是怎么计算竖直方向的周长呢?我们只需要统计竖直方向的竖线的个数,再乘以高度即可,因此我们需要时刻维护 num 数组来记录竖线的个数(但是考虑到子区间可能重叠,因此用 lc, rc 分别表示左/右端点是否被覆盖到来判断是否重叠)。各个数组的维护方式如下(其中 Len 同上一题):

if(cover[node]) {
    // 映射回真实的长度
    len[node] = y[end-1] - y[start-1];
    num[node] = 2;
    lc[node] = true;
    rc[node] = true;
} else {
    len[node] = len[node * 2] + len[node * 2 + 1];
    num[node] = num[node * 2] + num[node * 2 + 1] - ((rc[node * 2] && lc[node * 2 + 1]) ? 2 : 0);
    lc[node] = lc[node * 2];
    rc[node] = rc[node * 2 + 1];
}

对于 num 来说,如果当前区间被直接覆盖,num 应该直接设为 2(左右端点),左右端点都被覆盖(lc, rc 为 true)。如果没有被直接覆盖,num 应该设为两个子区间的 num 值之和,若两个子区间中间有重叠,应该再减去 $2$,而左右端点的覆盖情况与子区间相同。

注意,应该在更新前求竖线的长度(否则竖线个数会偏多),再更新,再计算区间覆盖的差值。另外因为坐标不再是正值,排序后,dummy_line(line[0]) 的值应该手动设置一下(lines[0].x = lines[1].x;)。

代码#
#pragma clang optimize on
#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

void update_tree(vector<int>& cover, vector<double>& len, vector<int>& num, vector<bool>& lc, vector<bool>& rc, vector<double>& y, int node, int start, int end, int L, int R, int val) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    // !!! a[i] += val, i in [L, R]
    if (R < start || L > end) {
        return;
    } else if (L <= start && end <= R) {
        cover[node] += val;
        
        if(cover[node]) {
            // 映射回真实的长度
            len[node] = y[end-1] - y[start-1];
            num[node] = 2;
            lc[node] = true;
            rc[node] = true;
        } else {
            len[node] = len[node * 2] + len[node * 2 + 1];
            num[node] = num[node * 2] + num[node * 2 + 1] - ((rc[node * 2] && lc[node * 2 + 1]) ? 2 : 0);
            lc[node] = lc[node * 2];
            rc[node] = rc[node * 2 + 1];
        }
        return;
    } else if (end - start == 1) {
        // 区间长度为 1 就返回
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    update_tree(cover, len, num, lc, rc, y, left_node, start, mid, L, R, val);
    update_tree(cover, len, num, lc, rc, y, right_node, mid, end, L, R, val); // !! "mid" instead of "mid+1".
    
    if(cover[node]) {
        // 映射回真实的长度
        len[node] = y[end-1] - y[start-1];
        num[node] = 2;
        lc[node] = true;
        rc[node] = true;
    } else {
        len[node] = len[node * 2] + len[node * 2 + 1];
        num[node] = num[node * 2] + num[node * 2 + 1] - ((rc[node * 2] && lc[node * 2 + 1]) ? 2 : 0);
        lc[node] = lc[node * 2];
        rc[node] = rc[node * 2 + 1];
    }
}

struct Line {
    int type; // 1 represents in-bound, -1 represents out-bound
    double x;
    double y1, y2;
    bool operator <(const Line& rhs) const{
        return x < rhs.x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n) {
        vector<Line> lines(2*n+1);
        vector<double> y; // 用于离散化的数组
        y.reserve(2*n+1);
        int p = 1;
        for(int i = 1; i <= n; ++i) {
            double a, b, c, d;
            cin >> a >> b >> c >> d;
            
            lines[p].type = 1;
            lines[p].x = a;
            lines[p].y1 = b;
            lines[p++].y2 = d;
            lines[p].type = -1;
            lines[p].x = c;
            lines[p].y1 = b;
            lines[p++].y2 = d;
            y.push_back(b);
            y.push_back(d);
        }
        
        sort(lines.begin()+1, lines.end());
        lines[0].x = lines[1].x;
        
        sort(y.begin(), y.end());
        vector<double>::iterator end = unique(y.begin(), y.end());
        int N = int(end - y.begin());
        
        vector<int> cover(8*N+1, 0);
        vector<double> len(8*N+1, 0);
        vector<int> num(8*N+1, 0);
        vector<bool> lc(8*N+1, 0);
        vector<bool> rc(8*N+1, 0);
        
        double ans = 0, lastLen = 0;
        for(int i = 1; i <= 2*n; ++i) {
            lines[i].y1 = int(lower_bound(y.begin(), end, lines[i].y1) - y.begin() + 1);
            lines[i].y2 = int(lower_bound(y.begin(), end, lines[i].y2) - y.begin() + 1);
            
            ans += num[1]*(lines[i].x-lines[i-1].x);
            
            update_tree(cover, len, num, lc, rc, y, 1, 1, N, int(lines[i].y1), int(lines[i].y2), lines[i].type);

            ans += abs(len[1] - lastLen);
            lastLen = len[1];
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

扫描线 HDOJ 3265 Posters#

扫描线 HDOJ 3265 Posters

这题和 扫描线 POJ 1151 Atlantis 的区别在于中间被挖掉了一部分。如果还是用之前的方法,我们可能需要考虑如何 PushDown,因为之前每个出边都对应一个入边,因此不需要 PushDown。但是我们可以采用把矩形分块的方式,把一个矩形分成四部分考虑即可。

无需改动主要代码,只需要修正一下数组大小与数组的输入。另外,因为题目数据都是整数,把数据类型设置为 long long 可以过。
#pragma clang optimize on
#pragma GCC optimize(2)

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

void update_tree(vector<int>& cover, vector<long long>& len,vector<long long>& y, int node, int start, int end, int L, int R, int val) {
    // suppose that indices are from 1 to n. range: [start, end], [L, R]
    // !!! a[i] += val, i in [L, R]
    if (R < start || L > end) {
        return;
    } else if (L <= start && end <= R) {
        cover[node] += val;
        
        // 更新长度信息
        if(cover[node])
            // 映射回真实的长度
            len[node] = y[end-1] - y[start-1];
        else
            len[node] = len[node * 2] + len[node * 2 + 1];
        return;
    } else if (end - start == 1) {
        // 区间长度为 1 就返回
        return;
    }
    
    int mid = (end - start)/2 + start;
    int left_node  = node * 2;
    int right_node = node * 2 + 1;
    
    update_tree(cover, len, y, left_node, start, mid, L, R, val);
    update_tree(cover, len, y, right_node, mid, end, L, R, val); // !! "mid" instead of "mid+1".
    
    // 更新长度信息
    if(cover[node])
        // 映射回真实的长度
        len[node] = y[end-1] - y[start-1];
    else
        len[node] = len[node * 2] + len[node * 2 + 1];
}

struct Line {
    int type; // 1 represents in-bound, -1 represents out-bound
    double x;
    double y1, y2;
    bool operator <(const Line& rhs) const{
        return x < rhs.x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n) {
        if (n == 0) return 0;
        vector<Line> lines(8*n+1);
        vector<long long> y; // 用于离散化的数组
        y.reserve(8*n+1);
        int p = 1;
        for(int i = 1; i <= n; ++i) {
            long long x1, y1, x2, y2, x3, y3, x4, y4;
            cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
            
            lines[p].type = 1;
            lines[p].x = x1;
            lines[p].y1 = y1;
            lines[p++].y2 = y2;
            lines[p].type = -1;
            lines[p].x = x3;
            lines[p].y1 = y1;
            lines[p++].y2 = y2;
            
            lines[p].type = 1;
            lines[p].x = x3;
            lines[p].y1 = y4;
            lines[p++].y2 = y2;
            lines[p].type = -1;
            lines[p].x = x4;
            lines[p].y1 = y4;
            lines[p++].y2 = y2;
            
            lines[p].type = 1;
            lines[p].x = x3;
            lines[p].y1 = y1;
            lines[p++].y2 = y3;
            lines[p].type = -1;
            lines[p].x = x4;
            lines[p].y1 = y1;
            lines[p++].y2 = y3;
            
            lines[p].type = 1;
            lines[p].x = x4;
            lines[p].y1 = y1;
            lines[p++].y2 = y2;
            lines[p].type = -1;
            lines[p].x = x2;
            lines[p].y1 = y1;
            lines[p++].y2 = y2;
            
            y.push_back(y1);
            y.push_back(y2);
            y.push_back(y3);
            y.push_back(y4);
        }
        
        sort(lines.begin(), lines.end());
        sort(y.begin(), y.end());
        vector<long long>::iterator end = unique(y.begin(), y.end());
        int N = int(end - y.begin());
        
        vector<int> cover(8*N+1, 0);
        vector<long long> len(8*N+1, 0);
        long long ans = 0;
        for(int i = 1; i <= 8*n; ++i) {
            lines[i].y1 = int(lower_bound(y.begin(), end, lines[i].y1) - y.begin() + 1);
            lines[i].y2 = int(lower_bound(y.begin(), end, lines[i].y2) - y.begin() + 1);
//            cout << len[1] << " * " << (lines[i].x-lines[i-1].x) << " = " << len[1]*(lines[i].x-lines[i-1].x) << endl;
            ans += len[1]*(lines[i].x-lines[i-1].x);
            update_tree(cover, len, y, 1, 1, N, int(lines[i].y1), int(lines[i].y2), lines[i].type);
        }

        cout << ans << endl;
    }
    
    return 0;
}