Chapter 1 基础算法¶

知识¶

alt text

模板¶

1. 快速排序¶

C++
#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return; // 边界条件

    // 初始化初值, 尤其注重边界 (+1 / -1)
    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);
}

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

    for (int i = 0; i < n; i ++ ) cin >> q[i];

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n-1; i ++ ) cout << q[i] << " ";
    cout << q[n-1] << endl;

    return 0;
}

2. 归并排序¶

C++
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    // 边界条件
    if (l >= r) return;

    // 先处理子问题, 确保两个“子段”自己都有序
    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    // 再对两个子段进行cmp (tmp存的是"自小到大"序)
    int k = 0, i = l, j = mid + 1;
    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];
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n-1; i ++ ) cout << a[i] << " ";
    cout << a[n-1] << endl;

    return 0;
}

求逆序对 (数量):

C++
// 完全基于merge_sort()的模板
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int a[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;

    // 先处理子问题, 注意这里的result是两个子问题的"相加"
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            // |l---(i)---mid|mid+1----(j)--r|
            // 既然(i,j)构成了逆序对, 那么(i+1, ..., mid)也都构成
            res += 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 res;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}

3. 二分¶

(1) 整数二分:

给定一个按照升序排列的长度为 \(n\) 的整数数组，以及 \(q\) 个查询

对于每个查询，返回一个元素 \(k\) 的起始位置和终止位置（位置从 0 开始计数）

如果数组中不存在该元素，则返回 -1 -1

C++
// 边界问题要注意, 有两套模板, 针对的是不同的寻找区间
// |-------red-------||-------green-------|

// (1) 查找red的右边界: mid = (l+r+1) >> 1
mid = (l+r+1) >> 1;
l = mid;
r = mid-1;

// (2) 查找green的左边界: mid = (l+r) >> 1
mid = (l+r) >> 1;
r = mid;
l = mid+1;

代码模板:

C++
#include <iostream>

using namespace std;

const int N = 100010;

int n, m, x;
int q[N];

bool check_rhs(int mid)
{
    return q[mid] >= x;
}

bool check_lfs(int mid)
{
    return q[mid] <= x;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> q[i];

    while (m -- ) // 进行m次查询
    {
        cin >> x;

        // 寻找x的右边界: "green"
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (check_rhs(mid)) r = mid;
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' '; // ">=x"的min, 即: x的右边界

            // 寻找x的左边界: "red"
            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (check_lfs(mid)) l = mid;
                else r = mid - 1;
            }

            cout << l << endl; // "<=x"的max, 即: x的左边界
        }
    }

    return 0;
}

(2) 实数二分:

给定一个浮点数 \(n\)，求它的三次方根:

C++
// 不存在边界+1/-1问题, 但是要注意 "小数后几位" 这个写法
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;
    while (r - l > 1e-8) // double判等的写法 (依据题目要求的输出精度, 一般多2)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    // 比如, 题目要答案精确到1e-6, 判等的条件就是1e-8.

    cout << fixed << setprecision(6) << l << endl;
    return 0;
}

[!tip] 确定小数输出的精确位数头文件: #include<iomanip> 写法是: cout << fixed << setprecision(6) << xxx << endl;

4. 前缀和 (1D + 2D)¶

C++
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

/* 
求 [l, r] 的区间和: s[r] - s[l-1]
*/

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    // 1D前缀和的初始化
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];

    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl; // 1D区间和的计算
    }

    return 0;
}

C++
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
    /*
    // 加速:
    ios::sync_with_stdio(false);
    cin.tie(0);
    */

    cin >> n >> m >> q;

    // 2D前缀和的初始化-1
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> s[i][j]; // 本质: 每个点的2D前缀和数组先初始化成自身输入

    // 2D前缀和的初始化-2
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    while (q -- )
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl; // 2D区间和的计算
    }

    return 0;
}

[!tip] 加速IO std::ios::sync_with_stdio(false); std::cin.tie(0);

5. 差分 (1D + 2D)¶

C++
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N]; // a: 原数组 b: 对应的差分数组

void insert(int l, int r, int c)
{
    // 操作目的: a[l~r] += c
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    // 差分数组初始化
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);

    // 具体insert操作
    while (m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    // 对 差分数组b 求前缀和 <=> 原数组a
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;
}

C++
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

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

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

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> a[i][j];

    // 二维差分数组 初始化
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);

    // 具体insert操作
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    // 对 差分数组b 求前缀和 <=> 原数组a
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) cout << b[i][j] << " ";
        cout <<endl;
    }

    return 0;
}

6. 双指针¶

左右指针：两个指针，相向而走，中间相遇
快慢指针：两个指针，有快有慢，同向而行

(1) 数组元素的目标和: a[] 和 b[] 各自升序, 求 a[i] + b[j] == x 的 (i, j) 元组数

左右指针

C++
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m, x;
int a[N], b[N];

int main()
{
    cin >> n >> m >> x;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];

    // 相较于O(n^2)的遍历, 这种的优势是: j 一旦不合理就直接结束, 复杂度大幅降低
    for (int i = 0, j = m - 1; i < n; i ++ )
    {
        while (j >= 0 && a[i] + b[j] > x) j -- ;
        if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    } // 必须要 j>=0 !!!

    return 0;
}

(2) 判断子序列: 如序列 {\(a1\),\(a3\),\(a5\)} 是序列 {\(a1\),\(a2\),\(a3\),\(a4\),\(a5\)} 的一个子序列

快慢指针

C++
// 整个过程中j指针不断扫描b数组并且向后移动，相当于不断给i指针所指向的a数组创建匹配的机会，只有匹配成功时i指针才会向后移动一位，当i == n时，说明全部匹配成功
#include<iostream>
#include<cstdio>
using namespace std;

const int N=1e5+10;

int a[N],b[N];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];

    int i = 0;
    for(int j = 0; j < m; j++) // j -> b[]
    {
        if (i < n && a[i] == b[j])  i++; 
    } // 必须要 i<n !!!

    if (i == n) puts("Yes");
    else puts("No");
    return 0;
}

7. 位运算¶

(1) 求一个数的二进制中1的个数: 基于lowbit(x)

C++
int lowbit(int x) { // def: x 的二进制表示中, 最后一个1 + 全0 所构成的整数
    // x = 1100
    // lowbit(x) = 100
    return x & (-x);
}

for (int i = x; i; i -= lowbit(i)) num++;

(2) 后续的 "快速幂" 之类的...

C++
// 一个数乘(除) 2 的非负整数次幂
int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}

int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

// 判断两非零数符号是否相同
bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

// 操作一个数的二进制位

// (1) 获取 a 的第 b 位. 最低位编号为 0
int getBit(int a, int b) { 
    return (a >> b) & 1; 
}

// (2) 将 a 的第 b 位设置为 1. 最低位编号为 0
int setBit(int a, int b) { return a | (1 << b); }

// (3) 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

// (4) 将 a 的第 b 位取反. 最低位编号为 0
int flapBit(int a, int b) { return a ^ (1 << b); }

8. 区间合并¶

纯模板: 先按左端点排序，再维护一个区间，与 “后来者区间” 进行三种情况的比较 (尾部)

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII; // 默认是按照左端点排序

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9; // 初始化
    for (auto seg : segs)
        if (ed < seg.first) // 需要另立门户
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second); // 直接尾加

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

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

    vector<PII> segs;
    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;
}

9. 高精度算法¶

(1) 高精度加法

做法:

Text Only
用 a, b 两个字符串存储输入。a = 567, b = 28
为了方便计算，将两个数分别 倒序 存放在 A， B 两个整数数组中。 A = [7, 6, 5], B = [8, 2]
新建整数数组 C 保存结果，整型变量 t 保存进位，初始 t = 0
将各个位上的数字相加，求出结果对应位上的数字和进位
    例如对个位计算： A[0] + B[0] = 7 + 8 = 15, 结果个位上是 5， 进位是 1. 所以 C[0] = 5, 进位 t = 1
最后把结果数组 C 中就保存了计算倒序结果，倒序输出就是答案

代码:

C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B)
{
    //为了方便计算，让A中保存较长的数字， B中保存较短的数字
    if (A.size() < B.size()) return add(B, A);
    //保存结果的数组
    vector<int> C;
    //进位，开始时是0
    int t = 0;
    //依次计算每一位
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];//加上 A 的第 i 位上的数字
        if (i < B.size()) t += B[i];//加上 B 的第 i 位上的数字
        C.push_back(t % 10); //C 中放入结果
        t /= 10;//t 更新成进位
    }
    //最后如果进位上有数，放进结果数组
    if (t) C.push_back(t);
    return C;//返回结果
}

int main()
{
    string a, b;//以字符串形式保存输入的两个整数
    vector<int> A, B;//保存两个整数的数组
    cin >> a >> 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];//倒序输出C中的数字
    cout << endl;
    return 0;
}

python 秒了:

Python
a = input()
b = input()
print(a+b)

(2) 高精度减法

减法的借位处理
相减为负数的处理
前导0的处理

C++
#include <iostream>
#include <vector>
using namespace std;

bool cmp(vector<int>& A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();  // 直接return 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector <int> sub(vector<int>& A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10 ); // 合而为1
        if(t < 0)  t = 1;
        else t = 0;

    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();  // 去掉前导0

    return C;
}

int main()
{
    string a ,b;
    vector<int> A, B;

    cin >> a >> 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--) printf("%d", C[i]);
        return 0;
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }

    return 0;
}

python 秒了:

Python
a = input()
b = input()
print(a-b)

(3) 高精度乘法

C++
#include<iostream>
#include<vector>
using namespace std;

vector<int> mul(vector<int> A,int b)
{
    vector<int> C;
    int t = 0;// 进位
    for(int i = 0; i < A.size(); i++){
        t = t + A[i] * b;
        C.push_back(t % 10);
        t = t / 10;
    }

    // 最后一次进位的结果还没有存储结束
    while(t)
    {
       C.push_back(t % 10);
       t = t / 10;
    }

    // 将高位的0一一弹出
    while(C.size() > 1 && C.back() == 0)
    {
        // vetcor数组的末端存储数字的高位
        C.pop_back();
    }

    return C;
}


int main()
{
    string a;
    int b;

    cin>>a;
    scanf("%d",&b);

    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }

    auto C = mul(A,b);

    // if(C[C.size() - 1] == 0)
    // {
    //     // 最高位是0 说明全部都是0
    //     cout<<0;
    //     return 0;
    // }

    for(int i = C.size() - 1; i >= 0; i--)
    {

        printf("%d",C[i]);
    }

    return 0;
}

python 秒了:

Python
a = input()
b = input()
print(a*b)

(4) 高精度除法

C++
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r)
{   
    // r传入r的地址，便于直接对余数r进行修改
    vector<int> C;
    for(int i=0;i<A.size();i++){//对A从最高位开始处理
        r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
        C.push_back(r/B);//所得即为商在这一位的数字
        r=r%B;
    }
    // 由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，
    // 因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int B,r=0; //代表余数
    cin>>a>>B;
    vector<int> A;
    for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理

    auto C = div(A,B,r);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
    cout<<endl<<r;//输出余数
    cout<<endl;
    return 0;
}

python 秒了:

Python
a = int(input())
b = int(input())
print(a//b)
print(a%b)

[!tip] python 基本的 I/O input() and print()

Python
>>> a = [1,2,3]; print(a[-1])  # 打印时默认末尾换行
3
>>> print(ans[0], ans[1])  # 可以输出任意多个变量，默认以空格间隔
1 2
>>> print(a[0], a[1], end='')  # 令 end='', 使末尾不换行
1 2>>>
>>> print(a[0], a[1], sep=', ')  # 令 sep=', '，改变间隔样式
1, 2
>>> print(str(a[0]) + ', ' + str(a[1]))  # 输出同上，但是手动拼接成一整个字符串

Python
>>> s = input('请输入一串数字: '); s  # 自己调试时可以向 input() 传入字符串作为提示
请输入一串数字: 1 2 3 4 5 6
'1 2 3 4 5 6'

10. 离散化¶

当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以 将原来的数据按照排名来处理 问题，即离散化

[!tip] 离散化常见使用场景当原始数据的值域非常大（例如 109）或者包含非整数，但我们只关心这些数据之间的相对大小关系时，就可以用离散化将这些庞大的值映射到 [1, n] 这个紧凑的整数范围内

类别1: 相同数值-映射到相同点¶

通常原数组中会有重复的元素，一般把相同的元素离散化为相同的数据

创建原数组的副本
将副本中的值从小到大排序
将排序好的副本去重
查找 原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值

[!tip] TLDR 相同数值-映射到相同点排序 --> 去重 --> 位置更新

模板写法 1: 普通数组

C++
// arr[i] 为初始数组,下标范围为 [1, n]

for (int i = 1; i <= n; ++i)  // step 1
    tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
    arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

正确性体现:

Text Only
init() ->
- arr = {105, 20, 777, 20, 99}
- tmp = {105, 20, 777, 20, 99}

==================================================================

std::sort(tmp + 1, tmp + n + 1) -> 
tmp = {20, 20, 99, 105, 777}

==================================================================

std::unique(tmp + 1, tmp + n + 1) - (tmp + 1); ->
得到去重后的 tmp 长度:

1. 它会把所有不重复的元素移动到数组的 最前面
2. 它会返回一个指向 "最后一个不重复元素" "之后位置" 的指针（迭代器）

std::unique 后, tmp 数组的内容变为 {20, 99, 105, 777, ?}

std::unique 返回的指针指向 777 的下一个位置，也就是 tmp[5] 的地址

- ?:  tmp[5]
- 20: tmp[1]

std::unique(...) - (tmp + 1) 指针减法, 得到4, 即为 tmp去重后 的区间长度len

==================================================================

lower_bound() 函数就像一个高效的图书管理员，它在一个 "排好序" 的书架上用 "二分法" 帮你找书

- tmp + 1: 查找区间的左端点
- tmp + 1 + len: 查找区间的右端点 (告诉管理员找到 tmp 数组的 第4个元素 之后 就停止)

完成任务后, 它返回的 不是数字3, 而是一个 指向 tmp数组中105这个元素存储位置 的 "指针"

==================================================================

finally, we have this:

{105, 20, 777, 20, 99} 被成功地离散化为: 
{3,   1,  4,   1,  2}

模板写法 2: vector

C++
// std::vector<int> arr;

std::vector<int> tmp(arr);  // tmp 是 arr 的一个副本
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
    arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

正确性体现:

TL; DR

类别2: 相同数值-映射到不同点¶

有时候会把 相同的元素根据输入顺序 离散化为不同的数据

结构体! 创建原数组的副本，同时记录每个元素出现的位置
将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序
将离散化后的数字放回原数组

模板写法:

C++
struct Data {
    int idx;
    int val;
}input[maxn];

bool cmp (Data a, Data b) {
    if (a.val == b.val) return a.idx < b.idx;
    return a.val < b.val;
}

for (int i = 1; i <= n; i++) cin >> arr[i]; // 原数组
for (int i = 1; i <= n; i++) input[i] = Data{i, arr[i]}; // idx捆绑
std::sort(input + 1, input + 1 + n);
for (int i = 1; i <= n; i++) arr[ input[i].idx ] = i;

正确性说明:

Text Only
arr = {105, 20, 777, 20, 99}

tmp[1] = {idx: 1, val: 105}
tmp[2] = {idx: 2, val: 20}
tmp[3] = {idx: 3, val: 777}
tmp[4] = {idx: 4, val: 20}
tmp[5] = {idx: 5, val: 99}

==================================================================

after std::sort(input + 1, input + 1 + n):

tmp[1] = {idx: 2, val: 20}
tmp[2] = {idx: 4, val: 20}
tmp[3] = {idx: 5, val: 99}
tmp[4] = {idx: 1, val: 105}
tmp[5] = {idx: 3, val: 777}

==================================================================

after arr[ input[i].idx ] = i:

arr[2] = 1: 把排名 1 写回到 arr[2]
arr[4] = 2: 把排名 2 写回到 arr[4]
...

->

finally:

arr = {4, 1, 5, 2, 3}

例题:

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

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;
    }
    // 因为后续的 前缀和 和 查询 都采用了 1-based 的数组下标
    return r + 1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c}); // {num_idx, val}

        alls.push_back(x); // num_idx
    }

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r}); // 查询区间

        alls.push_back(l); // num_idx
        alls.push_back(r); // num_idx
    }

    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理插入
    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];

    // 处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}