按视频敲代码顺序，逐个解释函数

导读

• double坐标(区间)：指题目给定的最原始输入的double类型的值，用ys数组存
• 离散化后坐标(区间)：double坐标在原数组ys中的下标(index)，也是double值离散化后的结果 [y_1, y_2, ...]
  • double坐标 –> 离散化后的坐标：用find函数: 离散化后的坐标 = find(double坐标)
  • 离散化后的坐标 –> double坐标：double坐标 = ys[离散化后的坐标]
• 线段树中的区间(Node)：指线段树中的某个节点tr[u]所表示的 线段树的区间[tr[u].l,tr[u].r]

一定要搞清楚这三个值之间的关系

• double值通过离散化与离散化后的值一一对应
• 线段树中的区间与离散化后的区间一一对应：线段树的Node节点tr[u]所表示的线段树中的区间[tr[u].l,tr[u].r]维护离散化后的区间[y_l, y_r + 1]

代码主体

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
vector<double> ys;

struct Segment
{
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}seg[N * 2];

struct Node
{
    int l, r;
    //线段树的节点tr[u]表示的线段树Node区间[tr[u].l,tr[u].r]维护离散化后的区间 --> [y_l, y_r + 1]
    int cnt;  //当前区间被覆盖的次数
    double len;  //当前区间被覆盖的长度
}tr[N * 2 * 4];

int find(double y)  //double坐标-->离散化后的坐标
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();  //返回区间中第一个>=y的数字的下标
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++ )
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[j ++ ] = {x1, y1, y2, 1};  //读入2n个线段 seg里存的是double坐标
            seg[j ++ ] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);  //所有y坐标存进ys里，待离散化
        }

        //对ys离散化
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        //离散化后纵坐标有2n个点， 2n-1个区间，构建线段树，线段树的节点维护这些区间tr[i] --> [y_i, y_i+1]，所以线段树的节点个数与区间个数相同2n-1
        build(1, 0, ys.size() - 2);  //从1号点开始建线段树，对应的离散化后的坐标的取值范围是0~ys.size()-2 --> 2n-1个

        //对线段按x排序：从左往右做
        sort(seg, seg + n * 2);

        double res = 0;
        for (int i = 0; i < n * 2; i ++ )  //依次处理每个seg
        {
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);  //计算答案
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);  //把当前seg作用到线段树上
            //这里一定要把double区间 变换到 线段树表示的区间 
            //线段树的节点 维护 离散化后的区间：tr[u] --> [tr[u].l,tr[u].r] --> [y_l, y_r + 1]
            //double的区间: seg[i].y1~seg[i].y2
            //离散化后的区间： find(seg[i].y1)~find(seg[i].y2)
            //线段树中的区间： find(seg[i].y1)~find(seg[i].y2)-1
        }

        printf("Test case #%d\n", T ++ );
        printf("Total explored area: %.2lf\n\n", res);
    }

    return 0;
}

build函数

• 扫描线中的build函数与普通线段树中的build函数相同

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        //新建线段树，因为是对每个seg计算过后再用modify加入到线段树中，所以在build时不需要pushup
    }
}

pushup函数

• 扫描线中的pushup函数与普通线段树中的pushup函数不同
• 普通线段树pushup函数的功能：通过children节点的信息更新parent节点的信息：只在chilren节点发生变化时pushup
• 扫描线pushup函数的功能：通过当前节点的cnt计算当前节点的len/通过children节点的len计算当前节点的len，所以当前节点的的cnt变化/children节点的信息变化时均要pushup

void pushup(int u)
{
    //如果当前节点被覆盖次数>0[覆盖满了]，那么直接计算当前节点所表示的真实区间的长度
    //tr[u]表示离散化后的区间 [tr[u].l, tr[u].r + 1] 外面套一层ys表示double值
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; 

    //否则，如果当前节点被覆盖的次数==0[没覆盖满]， 且不是叶子节点：有孩子节点
    else if (tr[u].l != tr[u].r)  //当前节点被覆盖的次数==0[没覆盖满]，通过孩子节点计算当前区间的len
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    //当前节点被覆盖的次数==0[没覆盖满]， 且是叶子节点
    else tr[u].len = 0;  //是叶子节点，则节点len为0
}

modify函数

• 扫描线中的modify函数与普通线段树中的modify函数不同
• modify函数的功能：修改cnt

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);  //多了一步pushup操作 当前Node的cnt有变化，则也会影响当前Node的len，也会pushup
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}