# ZeroJudge f855. 線段覆蓋長度 加強版

[ZeroJudge f855. 線段覆蓋長度 加強版](https://zerojudge.tw/ShowProblem?problemid=f855)

## 題意

同[b966. 第 3 題 線段覆蓋長度](https://zerojudge.tw/ShowProblem?problemid=b966)。
給定數個一維數線上的線段，求這些線段的所覆蓋的長度(所以重複不算)。

## 解法

有三種做法：排序+掃描線、離散化(map)+差分、離散化(sort + unique)+差分

### 離散化(map)+差分

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

map<int, int> m;

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        ++m[l], --m[r];
    }
    auto it = m.begin();
    int now = it->second, prev = it->first, ans = 0;
    for (++it; it != m.end(); ++it) {
        if (now) {
            ans += it->first - prev;
        }
        now += it->second;
        prev = it->first;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
}

### 離散化(sort + unique)+差分

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define ALL(x) (x).begin(), (x).end()
#define discrete(x) sort(ALL(x)), x.resize(distance((x).begin(), unique(ALL(x))));
#define query(x, i) lower_bound(ALL(x), i) - (x).begin()
#define SZ(x) (int)x.size()

using namespace std;

int line[20050];

void solve() {
    int n;
    cin >> n;
    vector<int> L(n), R(n);
    for (int i = 0; i < n; ++i) {
        cin >> L[i] >> R[i];
    }
    vector<int> vec;
    vec.assign(ALL(L)), vec.insert(vec.end(), ALL(R));
    discrete(vec);
    for (int i = 0; i < n; ++i) {
        ++line[query(vec, L[i])], --line[query(vec, R[i])];
    }
    int ans = 0, now = 0;
    for (int i = 0; i < SZ(vec); ++i) {
        if (now) {
            ans += vec[i] - vec[i - 1];
        }
        now += line[i];
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
}

### 排序+掃描線

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> vec(n);
    for (auto &[a, b] : vec) {
        cin >> a >> b;
    }
    sort(vec.begin(), vec.end());
    int ans = 0;
    pair<int, int> unionSet = vec[0];
    for (int i = 1; i < n; ++i) {
        if (vec[i].first > unionSet.second) {
            ans += unionSet.second - unionSet.first;
            unionSet = vec[i];
        } else if (vec[i].second > unionSet.second) {
            unionSet.second = vec[i].second;
        }
    }
    ans += unionSet.second - unionSet.first;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
}