常用基础算法及例题(快速选择、归并求逆序对个数、二分、高精度、前缀和与差分、双指针、位运算、离散化、区间合并)

文章目录

一、基础算法(上)

1 快速排序模板2 快速选择的两种模板3 归并排序模板4 求逆序对的数量5 整数二分6 浮点数二分 二、基础算法(中)

1 高精度

I 高精度加法II 高精度减法III 高精度乘法IV 高精度除法 2 前缀和

I 一维II 二维 3 差分

I 一维II 二维 三、基础算法（下）

1 双指针算法

I 最长连续不重复子序列II 数组元素的目标和III 判断子序列 2 位运算

I n的二进制表示中的第k位II 返回x的最后一位1 lowbit(x)III 让x的最低位1变成0IV 二进制中1的个数 3 离散化4 区间合并

一、基础算法(上) 1 快速排序模板

  这个模板的好处是如果应对全部相同的元素3 3 3 3 3 3 3,它一样可以保持每次都能取到接近中点的位置，这样应对这种情况时，时间复杂度可以保持在O(nlogn),而其他写法如果遇到全部相同的元素会因为每次都只能舍掉1个元素而导致会递归n层，使得时间复杂度变为O(n^2)。

void quick_sort(int* q, int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

2 快速选择的两种模板

快速选择算法：

  思路：一次快排单趟后，左边区间的数是小于等于右边区间的数的，假设左边区间的元素个数是Sl,右边区间的元素个数是Sr。

  如果k <= Sl,那么第k小的数一定在左边区间，递归处理左边区间，找左边区间的第k个数；

  如果k > sl,那么第k小的数一定在右半区间，递归处理右边区间，找右半区间的第k - sl个数。

  假设每次都均匀二分，时间复杂度计算：
第 一 次 单 趟 长 度 n 第 二 次 单 趟 长 度 n 2 第 三 次 单 趟 长 度 n 4 . . . 所 以 总 的 计 算 长 度 为 n + n 2 + n 4 + . . . = n ( 1 + 1 2 + 1 4 + . . . ) < 2 n 所 以 时 间 复 杂 度 为 O ( n ) 第一次单趟长度n\ 第二次单趟长度frac{n}{2}\ 第三次单趟长度frac{n}{4}\ ...\ 所以总的计算长度为n + frac{n}{2} + frac{n}{4}+...=n(1 + frac{1}{2} + frac{1}{4} + ...)<2n\ 所以时间复杂度为O(n) 第一次单趟长度n第二次单趟长度2n​第三次单趟长度4n​...所以总的计算长度为n+2n​+4n​+...=n(1+21​+41​+...)<2n所以时间复杂度为O(n)
  如果直接排序，那么时间复杂度是O(nlogn)，如果使用快速选择算法，时间复杂度是O(n)

#include 
using namespace std;

const int N = 1e6 + 10;

int q[N];

int quick_select(int* q, int l, int r, int k)
{
    
    if (l == r) return q[l];
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1;
    
    if (sl >= k) return quick_select(q, l, j, k);
    else return quick_select(q, j + 1, r, k - sl);
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> q[i];
    cout << quick_select(q, 0, n - 1, k) << endl;
    return 0;
}

  另一种快速选择模板：

  这种要返回最小的k个数或最大的k个数的大概都有三种解法：sort、priority_queue、快速选择，其中快速选择的模板如下：

class Solution {
public:
    vector getLeastNumbers(vector& arr, int k) 
    {
        if (k == 0) return {};
        
        quick_select(arr, 0, arr.size() - 1, k);
        return {arr.begin(), arr.begin() + k};
    }
    void quick_select(vector& arr, int l, int r, int k)
    {
        int i = l - 1, j = r + 1, x = arr[(l + r) >> 1];
        while (i < j)
        {
            do i++; while (arr[i] < x);
            do j--; while (arr[j] > x);
            if (i < j) swap(arr[i], arr[j]);
        }
        int sl =  j - l + 1;
        
        if (k < sl) quick_select(arr, l, j, k);
        else if (k > sl) quick_select(arr, j + 1, r, k - sl);
    }
};

3 归并排序模板

const int N = 100010;
int tmp[N];
void merge_sort(int* q, int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) >> 1;
    int i = l, j = mid + 1, k = 0;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; ++i, ++j)
    {
        q[i] = tmp[j];
    }
}

4 求逆序对的数量

思路：

  那么怎么快速统计一半在左半区间一半在右半区间的逆序对个数呢，见下图：

  其实假设merge_sort会把该区间的逆序对个数返回，靠得也是分到最底层时下面的归并的过程。

  INT_MAX大概是2 * 10^9,超过3 * 1e9就会爆int，本题最大的逆序对数量是全部逆序时，假设数组长度为n，则n - 1 + n - 2 + ... + 1 = n^2 / 2，代入n = 1e5得最大逆序数量为5 * 1e9,会爆int，所以用long long

#include 
using namespace std;

const int N = 1e5 + 10;

int tmp[N];
int q[N];
typedef long long LL;

LL merge_sort(int* q, int l, int r)
{
    
    if (l >= r) return 0;
    int mid = (l + r) >> 1;
    //加左区间的逆序对数量和右区间的逆序对数量
    LL ret = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    //归并 同时处理q[i] > q[j]这种左端点在左区间 右端点在右区间的逆序对数量mid - i + j
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else
        {
            
            ret += mid - i + 1;
            tmp[k++] = q[j++];
        }
    }
    //扫尾
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    //归并回去
    for (i = l, j = 0; i <= r; ++i, ++j)
    {
        q[i] = tmp[j];
    }
    return ret;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];
    cout << merge_sort(q, 0, n - 1) << endl;
    return 0;
}

5 整数二分

  有单调性的题目一定可以二分，但是可以二分的题目不一定有单调性。

  本质：可以把区间一分为2，左半边是满足性质1的，右半边是满足性质2的，则二分一定可以找到区间的边界，即找到满足此性质的最右边一个点。

  一般选择两种模板的方式是先建模check，然后根据此时区间的更新方式选择是用I还是II,如果更新方式是l = mid，则mid = (l + r + 1) >> 1;，如果更新方式是r = mid,那么mid = (l + r) >> 1;

  l = mid更新时+1的原因，如果l = r - 1时，由于C++是向下取整，l + r / 2就等于l,不变，就死循环了。

例题：

#include 
using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    int x;
    while (q--)
    {
        cin >> x;
        
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (a[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';
            
            l = 0, r = n - 1;
            while (l < r)
            {
                
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

  总结：每次都要选择答案所在的区间进行处理，无解的情况是题目可能无界，模板不会无界，因为定义的性质肯定有边界，这个模板一定可以找到这个边界，一般我们都是用二分出的边界来判断题目是否有解。

6 浮点数二分

  浮点数二分不存在向下整除的边界问题，所以直接二分就可以了，不用像上面那样处理边界mid = (l + r) / 2 或 mid = (l + r + 1) / 2.

例题：

#include 
using namespace std;

int main()
{
    double x;
    cin >> x;
    double l = -10000, r = 10000;
    while (r - l >= 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    printf("%.6lfn", r);
    return 0;
}

二、基础算法(中) 1 高精度 I 高精度加法

  大整数的位数极端情况下大概有1e6位，大整数加法是两个1e6位的大整数加法。

  大整数的储存是存到一个数组里头去，存储数据时，低位存到数组的低位更好一些，这样可以方便的处理进位的问题。

模板

#include 
#include 
#include 
using namespace std;

vector add(const vector& A, const vector& B)
{
    int carry = 0;
    vector C;
    int i = 0, j = 0;
    while (i < A.size() || j < B.size() || carry != 0)
    {
        int tmp = (i == A.size() ? 0 : A[i++]) + (j == B.size() ? 0 : B[j++]) + carry;
        C.push_back(tmp % 10);
        carry = tmp / 10;
    }
    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector A;
    vector B;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    return 0;
}

II 高精度减法

A i − B i − t i f 上 面 小 于 0 , A i + 10 − B i − t 向 下 一 位 借 位 e l s e , A i − B i − t 即 可 A_i - B_i - t\ if上面小于0,A_i + 10 - B_i - t 向下一位借位\ else,A_i-B_i-t即可 Ai​−Bi​−tif上面小于0,Ai​+10−Bi​−t向下一位借位else,Ai​−Bi​−t即可

模板

#include 
#include 
#include 
using namespace std;



bool cmp(const vector& A, const vector& B)
{
    
    if (A.size() != B.size()) return A.size() > B.size();
    
    for (int i = A.size() - 1; i >= 0; --i)
    {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

vector sub(const vector& A, const vector& B)
{
    
    vector C;
    int t = 0;
    for (int i = 0; i < A.size(); ++i)
    {
        t = A[i] - (i < B.size() ? B[i] : 0) - t;
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}


int main()
{
    string a, b;
    cin >> a >> b;
    vector A;
    vector B;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; --i) B.push_back(b[i]- '0');
    if (cmp(A, B))
    {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    }
    else
    {
        auto C = sub(B, A);
        cout << '-';
        for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    }
    return 0;
}

III 高精度乘法

  算法思想：高精度A乘短长度的b，把b看成一个整体，结果的每一位都等于(A[i] * b + t) % 10,然后更新进位为t = (A[i] * b + t) / 10

#include 
#include 
#include 
using namespace std;

vector mul(const vector& A, const int b)
{
    vector C;
    int t = 0;
    int i = 0;
    while (i < A.size() || t != 0)
    {
        t = (i < A.size() ? A[i] : 0) * b + t;
        C.push_back(t % 10);
        t /= 10;
        i++;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}


int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector A;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    return 0;
}

IV 高精度除法

  本除法是一个高精度整数除以一个低精度整数b，把大整数A从高位往低位排，排成AnAn-1...A0,初始时余数r等于An,每次都求一个余数r整除b的值，商到结果C的back去，然后更新余数为(r % b) * 10 + An-1,循环下去，直到走完A0

#include 
#include 
#include 
#include 
using namespace std;

vector div(const vector& A, const int b, int& r)
{
    vector C;
    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;
}


int main()
{
    string a;
    int b;
    cin >> a >> b;
    int r = 0;
    vector A;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >=0; --i) cout << C[i];
    cout << endl << r << endl;
}

2 前缀和 I 一维

  假设有一个长度为n的数组：a1 , a2, a3, ..., an,前缀和定义为Si = a1 + a2 + ... + ai.

  如何求Si?Si有什么用？

  怎么求前缀和？ 利用递推公式Si = Si-1 + ai(定义S0 = 0)

  作用：快速求出原数组中一段数的和 al + al+1 + ... + ar = Sr - Sl-1,此操作是O(1)的。

  为什么下标要从1开始，是为了定义S0,这样方便用统一的公式。

模板：

#include 
using namespace std;
const int N = 1e6 + 10;

int a[N];
int s[N];

int main()
{
    int n, m;
    int l, r;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    while (m--)
    {
        scanf("%d %d",&l, &r);
        printf("%dn", s[r] - s[l - 1]);
    }
    return 0;
}

II 二维

  Sij表示以(1,1)到(i,j)组成的长方形内的元素的和。

  怎么求？递推公式推导如图：

  作用：求(x1, y1)为左上顶点，(x2, y2)为右上顶点的矩形中所有元素的和。

模板代码：

#include 
using namespace std;

const int N = 1010;

int a[N][N];

int s[N][N];

int main()
{
    int n, m , q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
        }
    }
    
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    
    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%dn", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

  观察边界：

3 差分 I 一维

  假设给定数组a1, a2, ..., an，需要构造数组b1, b2, ..., bn使得ai = b1 + b2 +...+ bi，即构造一个b数组使得a数组是b数组的前缀和，则b数组称为a数组的差分。

  可以发现前缀和和差分是一对逆运算。

  定义b1 = a1,其余情况bi = ai - a(i-1)即可。

  差分的作用：

O(n)的时间由b数组得到a数组。如果有一堆操作，要求给a数组的区间[l, r]的每个值都加c,如果利用差分，可以让每个操作都是O(1)的，如果要得到增加后了的a数组，则可以用一个O(n)的操作由b数组得到a数组，具体的操作就是bl + c, b(r+1) - c.

  差分的构造过程可以视为原始a数组全0，因此差分数组b也是全0，然后对(1,1)区间加a1…对(n,n)区间加an,所以差分不需要构造操作，只需要插入操作就可以了。

模板：

#include 
using namespace std;

const int N = 1e6 + 10;

int a[N];
int b[N];

void Insert(int* gap, int l, int r, int c)
{
    gap[l] += c;
    gap[r + 1] -= c;
}

int main()
{
    int n, m;
    int l, r, c;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
    {
        Insert(b, i, i, a[i]);
    }
    while (m--)
    {
        scanf("%d%d%d", &l, &r, &c);
        Insert(b, l, r, c);
    }
    for (int i = 1; i <= n; ++i)
    {
        a[i] = a[i - 1] + b[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

II 二维

  定义一个矩阵A，构造矩阵B使得矩阵A的元素aij是矩阵B(1,1)到(i,j)的前缀和，那么B矩阵就是A矩阵的差分矩阵。

  二维差分的主要作用是是给A的某个子矩阵加上值c，这个操作是O(1)的。

  所以这里初始化可以这样想：首先假定A矩阵全部值都是0，则B矩阵全部值都是0，然后对A的每个点的赋值可以看做是给每个子矩阵(i,j)-(i,j)插入一个a[i][j]，构造差分矩阵的过程可以归类到插入操作中。

#include 
using namespace std;

const int N = 1010;

int a[N][N];
int b[N][N];

void Insert(int b[N][N], int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 +1][y2 + 1] += c;
}

int main()
{
    int n, m , q;
    int x1, y1, x2, y2, c;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
        }
    }
    
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            Insert(b, i, j, i, j, a[i][j]);
        }
    }
    
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        Insert(b, x1, y1, x2, y2, c);
    }
    
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            a[i][j] = b[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cout << a[i][j] << ' ';
        }
        cout  << endl;
    }
    return 0;
}

三、基础算法（下） 1 双指针算法

  总共大概两大类：

  双指针算法的核心思想：把O(n^2)的暴力遍历优化成O(n).

  大概模板：

for (int i = 0, j = 0; i < n; ++i)
{
    //j合法且满足某种性质则j++
    while (j < n && check(i, j)) ++j;
    //每个题目的具体逻辑
}

I 最长连续不重复子序列

  一般这种双指针的题可以先想一下朴素做法，

//枚举终点
for (int j = 0; j < n; ++j)
{
    //枚举起点
    for (int i = 0; i <= j; ++i)
    {
        if (check(i, j)) ret = max(ret, j - i + 1);
    }
}

  其时间复杂度为O(n^2)(不考虑check的复杂度时)

  观察到假如定义i为以j结尾的串的最右边端点，会发现当j往后走的时候i一定会往后走或者不动，不可能往前走，因此可以改进如下：

for (int j = 0, i = 0; j < n; ++j)
{
    while (i <= j && check(i, j)) ++i;
    ret = max(ret, j - i + 1);
}

  这样两个指针最多走2n步了，复杂度就优化到O(n)了。

  双指针算法的本质就是发现某些性质（尤其是单调性），使得本来我们要枚举n^2个状态转化为枚举O(n)个状态。

  具体怎么检查i和j之间维护的是以j结尾的最长不重复子串见下面代码：

#include 
using namespace std;

const int N = 1e5 + 10;

int q[N];

int cnt[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];
    
    int ret = 0;
    for (int j = 0, i = 0; j < n; ++j)
    {
        
        ++cnt[q[j]];
        
        while (cnt[q[j]] > 1)
        {
            
            --cnt[q[i]];
            ++i;
        }
        ret = max(ret, j - i + 1);
    }
    cout << ret << endl;
}

II 数组元素的目标和

#include 
using namespace std;

const int N = 1e5 + 10;
int A[N];
int B[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n; ++i) cin >> A[i];
    for (int i = 0; i < m; ++i) cin >> B[i];
    
    for (int i = 0, j = m - 1; i < n; ++i)
    {
        while (j >= 0 && A[i] + B[j] > x) --j;
        if (A[i] + B[j] == x)
        {
            cout << i << ' ' << j;
            break;
        }
    }
    return 0;
}

III 判断子序列

#include 
using namespace std;
const int N = 1e5 + 10;

int a[N];
int b[N];

int main()
{
    int n, m;
    cin >> n >> m;
    int flag = 0;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    for (int i = 0, j = 0; i < n; ++i)
    {
        
        while (j < m && b[j] != a[i]) ++j;
        if (j == m)
        {
            cout << "No";
            flag = 1;
            break;
        }
        
        ++j;
    }
    if (flag == 0) cout << "Yes";
    return 0;
}

2 位运算 I n的二进制表示中的第k位

  这里规定个位为第0位。

先把n的第k位移动到个位n >>= k看看此时的n个位是几 n & 1综合:(n >> k) & 1

int main()
{
    int n;
    cin >> n;
    for (int k = 31; k >= 0; --k)
        cout << (n >> k & 1);
    return 0;
}

II 返回x的最后一位1 lowbit(x)

  这里准确的表述应该是返回x的最右边一位1，然后这个1往左都是0，往右也都是0.

lowbit(x) = x & (-x)

  原理：C++中，负数都是用补码储存的，所以-x = ~x + 1,设x = A 1 B,B是k个0,则~x = ~A 0 C,C是k个1，~x + 1 = ~A 1 B,x&(~x + 1) = 0 1 B,即我们要的答案。

III 让x的最低位1变成0

  x = x & (x - 1),证明类似上面。

IV 二进制中1的个数

思路1：

#include 
using namespace std;

int lowbit(int x)
{
    return x & (-x);
}

int main()
{
    int n, x, cnt;
    cin >> n;
    while (n--)
    {
        cin >> x;
        cnt = 0;
        while (x)
        {
            ++cnt;
            x -= lowbit(x);
        }
        cout << cnt << ' ';
    }
    return 0;
}

思路2：

#include 
using namespace std;

const int N = 1e6 + 10;
int q[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];
    for (int i = 0; i < n; ++i)
    {
        int cnt = 0;
        while (q[i] != 0)
        {
            q[i] &= (q[i] - 1);
            ++cnt;
        }
        cout << cnt << ' ';
    }
    return 0;
}

3 离散化

  在一组数据值域很大但是数据个数却不大的情况下，可以使用离散化的技术，所谓的离散化就是把一组数据映射到一组相同个数的连续的自然数，如：1 3 100 2000 500000 -> 0 1 2 3 4.

  离散化的两个问题：

用到的数据组成的a数组中可能有重复元素，需要排序再去重。如何算出x离散化后的值是多少，由于这时a数组是有序的，直接在a数组中二分查找x的位置即可。

  C++去重的库函数，对于一个vector alls，下面的代码可以完成排序加去重。

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin, alls.end()), alls.end());
//unique会把不重复的元素排在前面 重复的元素扔到后面 返回第一个重复的元素的迭代器
//然后erase掉就行


int find(const vector& q, int x)
{
    int l = 0, r = q.size() - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        
        if (q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;//映射到1~q.size()
}

例题：

  传统思路是我们开一个2 * 1e9个元素的数组，然后用前缀和来处理询问s[r] - s[l - 1]，但是请看我们仅有n个插入和m个询问,实际上需要的下标数是n个插入用的n个下标和m次询问用的2m个前缀和下标，n和m都是1e5数量级的，也就是说大概总共会用3* 1e5个下标，完全没有1e10的数量级.

  总范围是2 * 1e9，但是我们只用到了3 * 1e5个数，这就是典型的离散化应用场景。

  我们可以把用到的下标排个序，保序映射到从1开始的自然数序列。

  要给x下标的位置加c，等价于给x的离散化对应的字母k，对a[k] += c;

  要查询[l, r]的值的和，把l->k1, r->k2，然后求一下a[k1] + ... +a[k2]即可。

代码：

#include 
#include 
#include 
using namespace std;

typedef pair PII;
//插入n次 询问m次 一共用 n + 2m 级别个下标 
//所以离散化后的数组及其前缀和数组开为3 * 1e5级别
const int N = 3 * 1e5 + 10;
int a[N];
int s[N];

vector alls;
vector adds;
vector asks;


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;
    
    for (int i = 0; i < n; ++i)
    {
        int x, c;
        cin >> x >> c;
        adds.push_back({x, c});
    }
    
    for (int i = 0; i < m; ++i)
    {
        int l, r;
        cin >> l >> r;
        asks.push_back({l, r});
    }
    
    for (int i = 0; i < adds.size(); ++i)
    {
        alls.push_back(adds[i].first);
    }
    for (int i = 0; i < asks.size(); ++i)
    {
        alls.push_back(asks[i].first);
        alls.push_back(asks[i].second);
    }
    
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    for (auto e : adds)
    {
        int x = find(e.first);
        a[x] += e.second;
    }
    
    for (int i = 1; i <= alls.size(); ++i)
    {
        s[i] = s[i - 1] + a[i];
    }
    
    for (auto e : asks)
    {
        int l = find(e.first);
        int r = find(e.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

unique函数的实现算法：

vector::iterator unique(vector& a)
{
    
    int j = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        if (!i || a[i - 1] != a[i])
        {
            a[j++] = a[i];
        }
    }
    
    return a.begin() + j;
}

4 区间合并

  用途：有很多区间，若几个区间有交集（端点相交也算），则把这几个区间合并为一个比较长的区间。

模板题：

思路：

代码：

#include 
#include 
#include 
using namespace std;

typedef pair PII;
const int N = 1e6 + 10;

vector segs;

void merge(vector& segs)
{
    vector ans;
    //先假设一个[-2e9, -2e9]的区间作为起始
    int st = -2e9, end = -2e9;
    //先排序
    sort(segs.begin(), segs.end());
    for (auto seg : segs)
    {
        
        if (seg.first > end)
        {
            
            if (end != -2e9)
            {
                ans.push_back({st, end});
            }
            st = seg.first;
            end = seg.second;
        }
        
        else end = max(end, seg.second);
    }
    
    if (end != -2e9) ans.push_back({st, end});
    segs = ans;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}