1，快速排序

1）确定数组分界值x，可以是边界点、中点或者随机
2）调整区间，使第一个区间都小于x，第二个区间都大于x
3）递归处理左右两端区间

void q_sort(int q[], int l, int r) {
    if (l >= r) return;
    //x为数组中点值，而不是下标
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        while (q[++i] < x);
        while (q[--j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    q_sort(q, l, j);
    q_sort(q, j + 1, r);
}

2，归并排序

1）确定分界点下标为中点
2）递归排序左右两区间
3）采用双指针，用额外数组t存储，每次存储较小的数
4）将t数组的值复制到原数组

void meger_sort(int q[], int l, int r) {
    if (l >= r) return;
    //mid是中点下标
    int mid = l + r >> 1;
    //先归并左右区间
    meger_sort(q, l, mid);
    meger_sort(q, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (q[i] < q[j]) t[k++] = q[i++];
        else t[k++] = q[j++];
    }

    while (i <= mid) t[k++] = q[i++];
    while (j <= r) t[k++] = q[j++];

    for (int i = l, k = 0; i <= r;) q[i++] = t[k++];
}

3，整数二分

1）当将区间[l, r]划分成[l, mid]和[mid + 1, r]时， 其更新操作是r = mid或者l = mid + 1

    //r = mid的情况
    int l = 0, r = n - 1;
    while(l < r) {
        int mid = l + (r - l >> 1);
        if(check) r = mid;
        else l = mid + 1;
    }

1）当将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid
2）这里mid = l + (r - l + 2 >> 1)，是因为整数除法是向下取整，后面更新的时候有l = mid,
如果mid向下取整后为l，则会陷入死循环

    //l = mid 的情况
    int l = 0, r = n - 1;
    while(l < r) {
        int mid = l + (r - l + 2 >> 1);
        if(check) l = mid;
        else r = mid - 1;
    }

4，浮点数二分

由于浮点数没有取整的情况，所以不用考虑+1, l和r也直接等于mid即可

    double l = 0, r = n - 1;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(check) l = mid;
        else r = mid;
    }

5，高精度

高精度主要是对c++语言而言，比如两个1e6相加减，一个数的长度为1e6和一个数为1e9相乘除
主要是将字符串存储到vector中，然后再进行按每一位的算术运算

加法

vector<int> add(vector<int> A, vector<int> B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size() || t; i++) {
        //t为进位
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

减法

vector<int> sub(vector<int> A, vector<int> B) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i++) {
        //首先减掉借位
        t = A[i] - t;
        //看B处还有没有对应的数值
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        //看有无借位
        t = t < 0 ? 1 : 0;
    }
    //去掉前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

乘法

vector<int> mul(vector<int> A, int b) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || t; i++) {
        //每一位依次乘以b
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    //如果b等于0，只取最后一位0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

除法

vector<int> div(vector<int> &A, int &b, int &r) {
    vector<int> C;
    r = 0;
    //除法从高位开始
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

6，前缀和

    //一般下标从1开始
    //s数组即为a数组的前缀和
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    //a[l] + ... + a[r] = s[r] - s[l - 1]

7，差分

    //在区间[l, r]上加上c
    void insert(int l, int r, int c) {
        b[l] += c;
        b[r + 1] -= c;
    }
    
    //b是a的差分数组，a是b的前缀和
    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
    
    //求b的前缀和即为a
    for (int i = 1; i <= n; i++) b[i] += b[i - 1];

8，双指针

前面的快速排序、归并排序其实都是一种双指针算法
双指针算法包括：两个指针分别指向两个不同的序列；两个指针指向一个序列（比较常见）

一般双指针算法都会有以下形式：

for(int i = 0, j = 0; i < n; i++){
    while(j < i && check(i, j)) j++;
    //这里的check函数表示i，j满足某种性质
    //每道题目的具体逻辑
}

9，位运算

    求n的第k位数字: n >> k & 1
    返回n的最后一位1：lowbit(n) = n & -n

10，离散化

离散化主要用于对于值域很大，而数目很少的数组，将这样的数组映射到一个值域也差不多的数组中

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

//二分求出x对应的离散化的值
int find(int x){
    //找到第一个大于等于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;//映射到1,2...n;如果不加1是从0开始映射
}

11，区间合并

区间合并是指多个有交集的区间合并成一个区间，实际采用的是贪心算法
1）按区间左端点排序
2）扫描整个区间，将有交集的区间进行合并
如何合并?

1. 假设每个区间为[l, r]
2. 如果前一个区间是下一个区间的子集，则第一个区间左右端点不变
3. 如果前一个区间和下一个区间有交集，则 r 更新为第二的区间的 r
4. 如果前一个区间和下一个区间无交集，则前一个区间左右端点不变，找到一个无法合并的区间，并把下一个区间作为当前区间

    vector<PII> segs, res;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    //对区间进行排序
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;

    for (auto seg : segs) {
        //如果ed小于当前区间的起点
        if (ed < seg.first) {
            //如果st不是初始值，加入答案
            if (st != -2e9) res.push_back({st, ed});
            //更新st和ed
            st = seg.first;
            ed = seg.second;
        }
        //否则有交集，ed取最大值
        else ed = max(ed, seg.second);
    }
    //把最后一个区间加入答案
    if (st != -2e9) res.push_back({st, ed});

    cout << res.size() << endl;