描述

两种写法 build 线段树（用整数例子，小数与其同理）
1. 右端点向左偏移 <样例 1>
2. 拆分两个连续的区间（区间的左右端点表示与寻常线段树相同） <样例 2>

参考

https://www.cnblogs.com/dx123/p/17160008.html

https://www.bilibili.com/video/BV144411Z7tx/?spm_id_from=333.337.search-card.all.click&vd_source=d87d1ea029a4c499e954e1ab0af3e59f

<样例 3> 为本题AC代码

样例 1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ls (p << 1)
#define rs (p << 1 | 1)
const int N = 2E5 + 10;

struct L {
    int x1, x2, y, k;
    bool operator<(const L &t) const{return y < t.y; }
}line[N];

struct Node {
    int l, r, cnt, len;
}tr[N << 3];
int X[N];

void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void pushup(int p) {
    if (tr[p].cnt) tr[p].len = X[tr[p].r + 1] - X[tr[p].l];
    else tr[p].len = tr[ls].len + tr[rs].len;
}

void modify(int p, int l, int r, int k) {
    //if (tr[p].l > r || tr[p].r < l) return;
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].cnt += k;
        pushup(p);
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    if (l <= mid) modify(ls, l, r, k);
    if (r > mid) modify(rs, l, r, k);
    pushup(p);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        line[i] = {a, c, b, 1};
        line[i + n] = {a, c, d, -1};
        X[i] = a, X[i + n] = c;
    }

    n <<= 1;
    sort(line + 1, line + n + 1);
    sort(X + 1, X + n + 1);
    int s = unique(X + 1, X + n + 1) - X - 1;
    build(1, 1, s - 1);


    ll ans = 0;
    for (int i = 1; i <= n; i ++) {
        ans += 1LL * tr[1].len * (line[i].y - line[i - 1].y);

        int l = lower_bound(X + 1, X + s + 1, line[i].x1) - X;
        int r = lower_bound(X + 1, X + s + 1, line[i].x2) - X;
        modify(1, l, r - 1, line[i].k);
    }

    cout << ans << endl;

    return 0;
}

样例 2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ls (p << 1)
#define rs (p << 1 | 1)
const int N = 2E5 + 10;

struct L {
    int x1, x2, y, k;
    bool operator<(const L &t) const{return y < t.y; };
}line[N];

struct Node {
    int l, r, cnt, len;
}tr[N << 3];
int X[N];

void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0};
    if (r - l <= 1) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid, r);
}

void pushup(int p) {
    if (tr[p].cnt) tr[p].len = X[tr[p].r] - X[tr[p].l];
    else tr[p].len = tr[ls].len + tr[rs].len;
}

void modify(int p, int l, int r, int k) {
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].cnt += k;
        pushup(p);
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    if (l < mid) modify(ls, l, r, k);
    if (r > mid) modify(rs, l, r, k);
    pushup(p);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        line[i] = {a, c, b, 1};
        line[i + n] = {a, c, d, -1};
        X[i] = a, X[i + n] = c;
    }

    n <<= 1;
    sort(line + 1, line + n + 1);
    sort(X + 1, X + n + 1);
    int s = unique(X + 1, X + n + 1) - X - 1;
    build(1, 1, s);

    ll ans = 0;
    for (int i = 1; i <= n; i ++) {
        ans += 1LL * tr[1].len * (line[i].y - line[i - 1].y);
        int l = lower_bound(X + 1, X + s + 1, line[i].x1) - X;
        int r = lower_bound(X + 1, X + s + 1, line[i].x2) - X;
        modify(1, l, r, line[i].k);
    }

    cout << ans << endl;

    return 0;
}

样例 3

#include <bits/stdc++.h>

using namespace std;

#define ls (p << 1)
#define rs (p << 1 | 1)

const int N = 20010;

struct L {
    double x1, x2, y;
    int k;
    bool operator<(const L &t) const{return y < t.y; }
} line[N];

struct Node {
    int l, r, cnt;
    double len;
} tr[N << 3];
double X[N];

void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void pushup(int p) {
    if (tr[p].cnt) tr[p].len = X[tr[p].r + 1] - X[tr[p].l];
    else tr[p].len = tr[ls].len + tr[rs].len;
}

void modify(int p, int l, int r, int k) {
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].cnt += k;
        pushup(p);
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    if (l <= mid) modify(ls, l, r, k);
    if (r > mid) modify(rs, l, r, k);
    pushup(p);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int T = 0;
    cout << fixed << setprecision(2);

    while (cin >> n, n) {
        for (int i = 1; i <= n; i ++) {
            double a, b, c, d;
            cin >> a >> b >> c >> d;
            line[i] = {a, c, b, 1};
            line[i + n] = {a, c, d, -1};
            X[i] = a, X[i + n] = c;
        }

        n <<= 1;
        sort(line + 1, line + n + 1);
        sort(X + 1, X + n + 1);
        int s = unique(X + 1, X + n + 1) - X - 1;
        build(1, 1, s - 1);

        double ans = 0;

        for (int i = 1; i <= n; i ++) {
            ans += tr[1].len * (line[i].y - line[i - 1].y);
            int l = lower_bound(X + 1, X + s + 1, line[i].x1) - X;
            int r = lower_bound(X + 1, X + s + 1, line[i].x2) - X;
            modify(1, l, r - 1, line[i].k);
        }

        cout << "Test case #" << ++ T << '\n';
        cout << "Total explored area: " << ans << "\n\n";
    }

    return 0;
}