一、离散化
离散化的思想：
有一些数值，这些数构成的值域很大，但值的个数远小于值域
如：1，2，500，40000，3000000，1亿 值域[1,1亿]
有的题目可能要以这些值为下标来做，这时候不可能开一个长度为1亿的数组，因此就要把这个序列映射到从0开始连续的自然数： 0，1，2，3……
比如说数组 a[] ： 1，3，100，2000，50w
把它们映射到从0开始的自然数 0 1 2 3 4
这个过程就是离散化（其实就是把a中的值映射到各自的下标）

两个注意点：
①a[]中可能有重复数据：去重
模板：

vector<int> alls;  // 存储所有待离散化的数
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重

②如何算出x离散化后的值：因为a[]是有序的，可以用二分 （ ≥x区间的最左 ）
（本质就是找出x值在a[]中的下标是多少）

为什么可以离散化？
因为题目中只需用到这些数据间的相对大小关系，而不需要这些值的绝对大小

AcWing 802.区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是0。
现在，我们首先进行 n次操作，每次操作将某一位置 x上的数加 c。
接下来，进行 m次询问，每个询问包含两个整数l和r，你需要求出在区间[l,r]之间的所有数的和。

输入格式：
第一行包含两个整数n和m。
接下来 n行，每行包含两个整数 x和 c。
再接下来 m行，每行包含两个整数 l和 r。

输出格式：
共 m行，每行输出一个询问中所求的区间内数字和。

为什么这题能用离散化？因为只需要用到数据间的相对大小关系，包括插入数的坐标和查询的坐标，所有这些数的相对大小关系知道即可。

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

using namespace std;

const int N = 300010;
int a[N], s[N]; // a[]的下标就是离散化之后的结果，s[]用来求前缀和

vector<int> alls;  // 待离散化的数
vector<pair<int,int>> add, query;  // 所有要插入的位置x和在该位置上插入的数c构成的数对(x、c)命名为add、
                                   // 查询的坐标区间(l、r) 命名为query

// 离散化
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main()
{
    int n, m;
    cin >> n >> m;

    int x, c, l ,r;
    while ( n -- )
    {
        cin >> x >> c;
        add.push_back({x,c});
        alls.push_back(x);
    }

    while (m --)
    {
        cin >> l >> r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }

    // 排序 + 去重（模板）
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理插入（vecter add）
    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];

    // 处理询问（vertor query）
    for (int i = 0; i < query.size(); i ++)
    {
        int l = find(query[i].first), r = find(query[i].second);
        cout << s[r] - s[l - 1] << endl;
    }
}

二、区间合并
给定 n个区间 [li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和 [2,6]可以合并为一个区间 [1,6]。

输入格式
第一行包含整数 n。
接下来 n行，每行包含两个整数 l和r。

输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

思路：

始终保持一个当前维护区间，往右遍历新区间，新区间：
1° 左端点在当前维护区间的右端点右边的，把该新区间作为当前维护区间
2° 左端点<=当前维护区间的右端点的
(1)右端点 <= 当前维护区间的右端点，当前维护区间不变
(2)右端点 > 当前维护区间的右端点，当前维护区间更新，右端点更新为 新区间的右端点

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

using namespace std;

// 记录所有区间的数组，每一个区间是一个pair类型
vector<pair<int,int>> segs;

// 区间合并，计算合并后的区间个数
void merge(vector<pair<int,int>> &segs)
{
    vector<pair<int,int>> res;

    // 按区间左端点位置从小到大进行排序
    // sort函数中，pair类型默认优先以first 小到大排序，first相同的情况下按second排序
    sort(segs.begin(), segs.end());

    // 人为设置一个 初始当前维护区间
    int st = -2e9, ed = -2e9;

    for (auto seg : segs)
    {
        if (seg.first > ed)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }

    // 把最后一个区间加入数组中
    // if (st != -2e9)是为了防止输入的是空数组，数组里没有任何区间
    if (st != -2e9) res.push_back({st,ed});

    segs = res;
}

int main()
{
    int n;
    cin >> n;

    int l, r;
    while (n --)
    {
        cin >> l >> r;
        segs.push_back({l,r});
    }

    merge(segs);

    cout << segs.size();
}