AcWing 247. 亚特兰蒂斯

题目传送门

本题特殊一点就是支持小数，需要离散化，其它的和粉刷油漆那题一样的，不多说了：

#include 
using namespace std;

const int N = 100010;

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;
    int cnt;
    double len;
} tr[N * 8]; //由于线段二倍，所以8倍空间
vector ys; //用于离散化

//离散化+二分
int find(double y) {
    // 需要返回vector 中第一个 >= y 的数的下标
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u) {
    if (tr[u].cnt)
        tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l == tr[u].r)
        tr[u].len = 0;
    else
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    // 因为后面两个都是0, 所以不需要push_up;
}

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);
        // 扫描线 特殊在 修改[l, r]区间时，只需要修改父节点，不需要push_down操作来更新儿子节点
        // 因为只要父节点的tag > 0    永远没儿子节点什么事
        // 如果父节点的tag == 0, 那么把父节点push_up一下就行， 查询的时候只要输出父节点的长度就行， 同样也没儿子节点什么事
        // 所以即便是修改区间， 也不需要lazt_tag
    } 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);
    }
}

int main() {
    int n, T = 1;
    while (cin >> n, n) {
        ys.clear();
        int idx = 0;
        for (int i = 0; i < n; i++) {
            double x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            seg[idx++] = {x1, y1, y2, 1};
            seg[idx++] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }

        //离散化，之所以需要离散化，是因为y可能是小数，小数没法使用线段树，需要有映射的关系整数出现
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        //例子：假设现在有三个不同的y轴点,分为两个线段
        // y[0] ~ y[1],y[1] ~ y[2];
        //此时ys.size()为3,ys.size() - 2 为 1;
        //此时为 build(1, 0, 1);
        //有两个点0 和 1,线段树中0号点为y[0] ~ y[1],1号点为y[1] ~ y[2];
        build(1, 0, ys.size() - 2); //实践证明，多开2个也没啥问题

        //线段按x排序
        sort(seg, seg + idx);

        double res = 0;
        for (int i = 0; i < n * 2; i++) {
            //第一条竖边无法计算面积
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);   //根结点的len * 阴影部分高度
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k); //维护的是一小段区间
        }

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

    return 0;
}