基础算法

快速排序

快速排序

题干

给定你一个长度为 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 。

第二行包含 个整数（所有整数均在 范围内），表示整个数列。

输出格式

输出共一行，包含 个整数，表示排好序的数列。

数据范围

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

思路分析

快速排序（Quicksort）是一种高效的排序算法，采用分治法策略。其基本思想是：

1. 从数列中选择一个“基准”元素。
2. 重新排列数列，使得所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面（相同的元素可以放在任意一边）。在这个分区结束之后，该基准就处于数列的中间位置。
3. 递归地将小于基准元素的子数列和大于基准元素的子数列排序。
4. 当子数列的大小为零或一时，递归结束，因为这样的子数列已经是有序的。
5. 最终，所有子数列合并起来就形成了一个有序的数列。
6. 快速排序的平均时间复杂度为 。

快速排序在算法题中永远不会用到，因为STL的sort函数已经高度优化过了，直接调用即可；但是在面试题中可能会考，因此要记住代码。注意代码已经是高度优化过的，不要改动任何一个细节，任何改动都可能导致数组越界或者无限递归。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int a[N];

void quick_sort(int a[], int l, int r)
{
    // l >= r 终止防止无限递归
    if (l >= r) 
        return;

    // 由于用的是do-while循环，开始时i和j会先移动，因此初始化时i和j要比区间端点更靠外1位
    int i = l - 1, j = r + 1, x = a[(l + r)>> 1];
    while (i < j)
    {
        do{i++;} while(a[i] < x);
        do{j--;} while(a[j] > x);
        if (i < j)
            swap(a[i], a[j]);
    }
    // 由于j的循环逻辑，只有遇到a[j] <= x时才会停下，因此 j+1 到 r 全部 >= x，因此递归l到j和j+1到r即可

    quick_sort(a, l, j), quick_sort(a, j + 1, r);
    return;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    quick_sort(a, 1, n);
        
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
}

第k个数

题干

给定一个长度为 的整数数列，以及一个整数 ，请用快速选择算法求出数列从小到大排序后的第 个数。

输入格式

第一行包含两个整数 和 。

第二行包含 个整数（所有整数均在 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 小数。

数据范围

输入样例：

5 3
2 4 1 5 3

输出样例：

3

思路分析

本题只需要找到第 小的数，而不需要对整个数列进行排序，因此每次快速排序只需要遍历第 个数所在的一侧即可，时间复杂度为 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

int a[N];

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

    // 左半部分区间长度为 j - l + 1
    if (j - l + 1 >= k)
        return quick_sort(a, l, j, k);

    // 如果在右半部分，k 也要对应减少左半部分的长度
    return quick_sort(a, j + 1, r, k - (j - l + 1));
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    cout << quick_sort(a, 1, n, k) << '\n';
    return 0;
}

归并排序

归并排序

题干

给定你一个长度为 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 。

第二行包含 个整数（所有整数均在 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

思路分析

归并排序（Merge Sort）是一种高效的排序算法，采用分治法策略。其基本思想是：

1. 将待排序的数列分成两个子数列，分别对这两个子数列进行递归排序。
2. 将两个已排序的子数列合并成一个最终的排序数列。
3. 当子数列的大小为零或一时，递归结束，因为这样的子数列已经是有序的。
4. 最终，所有子数列合并起来就形成了一个有序的数列。
5. 归并排序的时间复杂度为 。
6. 归并排序是一种稳定的排序算法，因为在合并过程中，相等的元素不会改变它们的相对位置。

与快速排序从上到下进行排序不同，归并排序是从下到上进行排序的，先将小的子序列排序，再逐步合并成更大的有序序列，直到整个数列有序。这种从下到上的分支特点使得归并排序能计算一些需要分治的信息，比如逆序对数量等。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

int a[N], tmp[N];

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

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

逆序对的数量

题干

给定一个长度为 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 个和第 个元素，如果满足 且 ，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 ，表示数列的长度。

第二行包含 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

数列中的元素的取值范围 。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

思路分析

当区间长度较小时，很容易统计逆序对的数量，因此考虑用归并排序的分治思想来统计逆序对的数量。

不妨规定归并排序的返回值是 区间内的逆序对数量，则其由三部分组成：

1. 左半部分 的逆序对数量；
2. 右半部分 的逆序对数量；
3. 跨越左右两部分的逆序对数量。

前面两个部分我们可以用递归 merge_sort(l, mid) 和 merge_sort(mid + 1, r) 来计算，后半部分我们可以在排序的过程中统计。由于左半边每一个元素的下标均小于右半边的元素并且两边均已排序，因此当我们发现 a[i] <= a[j] 时，说明 a[i] 不会与右半边后续的元素构成逆序对，可以直接将其放入临时数组中；但当我们发现 a[i] > a[j] 时，说明 a[j] 会与左半边从 i 到 mid 的所有元素构成逆序对，因此可以将逆序对数量增加 mid - i + 1。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;

int a[N], tmp[N];

ll merge_sort(int a[], int l, int r)
{
    if (l >= r)
        return 0;
    int mid = l + r >> 1;
    
    // 计算左右两部分单独的逆序对数量
    ll res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
    
    int i = l, j = mid + 1, k = l;

    // 排序+计算横跨两部分的逆序对数量
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid)
        tmp[k++] = a[i++];
    while (j <= r)
        tmp[k++] = a[j++];
        
    for (int i = l; i <= r; i++)
        a[i] = tmp[i];
    
    return res;
}

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

二分

数的范围

题干

给定一个按照升序排列的长度为 的整数数组，以及 个查询。

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

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

输入格式

第一行包含整数 和 ，表示数组长度和询问个数。

第二行包含 个整数（均在 范围内），表示完整数组。

接下来 行，每行包含一个整数 ，表示一个询问元素。

输出格式

共 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

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

数据范围

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

思路分析

本题需要找到一个数在有序数组中的起始位置和终止位置，可以使用二分查找来实现。由于二分查找每次只能找到一个位置，因此需要分别进行两次二分查找：一次查找起始位置，一次查找终止位置。记住二分查找的模板即可，临界条件是l + 1 == r，也就是说结束时l和r其中一个会满足临界条件。以if (a[mid] < x) l = mid; else r = mid;为例，每次更新的l都是小于x的，r都是大于等于x的，因此最后结束时l,r相邻，得到l是最大的小于x的数，r是最小的大于等于x的数。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e5 + 10;

int a[N];

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

数的三次方根

题干

给定一个浮点数 ，求它的三次方根。

输入格式

共一行，包含一个浮点数 。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 位小数。

数据范围

输入样例：

1000.00

输出样例：

10.000000

思路分析

浮点数二分因为没有临界问题，较为简单。注意好临界条件就行，只要l和r的差值小于一定精度就可以停止。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 9;
const double eps = 1e-8;

int a[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    double n;
    cin >> n;
    double l = -N, r = N;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid < n)
            l = mid;
        else
            r = mid;
    }
    printf("%lf", l);
}

高精度

高精度加法

题干

给定两个正整数（不含前导 ），计算它们的和。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的和。

数据范围

输入样例：

12
23

输出样例：

35

思路分析

高精度加法的思路是将两个大整数从低位到高位逐位相加，并处理进位。由于输入的整数可能非常大，无法直接使用基本数据类型存储，因此我们可以将其存储为字符串，将字符串转化为vector进行逐位计算。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;

vector<int> A, B;

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(); i++)
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

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

高精度减法

题干

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。

输入格式

共两行，每行包含一个整数。

输出格式

共一行，包含所求的差。

数据范围

输入样例：

32
11

输出样例：

21

思路分析

高精度减法的思路是将两个大整数从低位到高位逐位相减，并处理借位。为了防止出现负数，因此我们先写一个cmp函数比较大小，确定被减数大于减数；如果被减数小于减数，就先打印负号再交换两数进行减法操作。

对于cmp函数，我们先比较两个向量的长度，如果长度不同，长度较大的数较大；如果长度相同，则从高位到低位逐位比较，如果不相同就返回较大的，如果相同就比较下一位，直到全部比完，如果此时仍然相同说明两个数相等，返回前者更大即可。

对于处理减法计算的过程，我们仍然是用一个 t 存储进位，每一次先用 t 加上被减数的当前位再减去减数的当前位，如果 t 小于 0，说明需要借位，将 t 加上 10 并将 t 设为 -1，表示下一位需要借位；否则将 t 设为 0。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;

vector<int> A, B;

bool cmp(vector<int> &A, vector<int> &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<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];
        if (i < B.size())
            t -= B[i];
        if (t >= 0)
        {
            C.push_back(t);
            t = 0;
        }
        else
        {
            C.push_back(t + 10);
            t = -1;
        }
    }
    while (t)
    {
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string 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--)
            cout << C[i];
    }
    else
    {
        auto C = sub(B, A);
        cout << '-';
        for (int i = C.size() - 1; i >= 0; i--)
            cout << C[i];
    }
}

高精度乘法

题干

给定两个非负整数（不含前导 ） 和 ，请你计算 的值。

输入格式

共两行，第一行包含整数 ，第二行包含整数 。

输出格式

共一行，包含 的值。

数据范围

,

输入样例：

2
3

输出样例：

6

思路分析

仿照高精度加法的思路即可，将大整数从低位到高位逐位与小整数相乘，并处理进位。每次将 t % 10 存入结果数组，并将 t / 10 作为进位传递到下一位。

#include <bits/stdc++.h>
using namespace std;

vector<int> A;

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

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

高精度除法

题干

给定两个非负整数（不含前导 ） ，请你计算 的商和余数。

输入格式

共两行，第一行包含整数 ，第二行包含整数 。

输出格式

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

,
,
一定不为

输入样例：

7
2

输出样例：

3
1

思路分析

与之前的三种计算都不同，除法需要从高位到低位进行计算。我们可以用 t 记录当前的余数，然后从高到低遍历。每次进入到下一位时，将 t 乘以 10 并加上当前位的数字，然后计算当前位的商 t / b 并将其存入结果数组中，最后更新余数 t % b。

由于这样求出来的商是从高位到低位存储的，这样不方便删去前导零，因此我们需要将结果向量反转，删除前导零后输出。

#include <bits/stdc++.h>
using namespace std;

vector<int> A;

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

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string a;
    int b;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(int(a[i] - '0'));
    auto C = div(A, b);
    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];
    cout << '\n' << t;
}

前缀和与差分

前缀和

题干

输入一个长度为 的整数序列。

接下来再输入 个询问，每个询问输入一对 。

对于每个询问，输出原序列中从第 个数到第 个数的和。

输入格式

第一行包含两个整数 和 。

第二行包含 个整数，表示整数数列。

接下来 行，每行包含两个整数 和 ，表示一个询问的区间范围。

输出格式

共 行，每行输出一个询问的结果。

数据范围

,
,

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

思路分析

前缀和是一种常见的思想，用于预处理数组前n项和，使得可以在时间内计算区间和。前缀和数组prefix[i]表示原数组第1到i项的和，因此区间[l, r]的和可以通过prefix[r] - prefix[l - 1]计算得到。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

int a[N];
int prefix[N];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] + a[i];
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << '\n';
    }
}

子矩阵的和

题干

输入一个 行 列的整数矩阵，再输入 个询问，每个询问包含四个整数 ，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 ，，。

接下来 行，每行包含 个整数，表示整数矩阵。

接下来 行，每行包含四个整数 ，表示一组询问。

输出格式

共 行，每行输出一个询问的结果。

数据范围

,
,
,
,

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

思路分析

二维前缀和是前缀和的扩展，用于处理二维矩阵的区间和问题。我们定义一个二维前缀和数组prefix[i][j]，表示从矩阵左上角到位置(i, j)的子矩阵的和。对于计算prefix[i][j]，我们可以使用以下关系：

对于任意子矩阵(x1, y1)到(x2, y2)的和，可以通过以下公式计算：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;

int a[N][N];
int prefix[N][N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m, q;
    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++)
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + a[i][j];
    while (q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1] << '\n';
    }
}

差分

题干

输入一个长度为 的整数序列。

接下来输入 个操作，每个操作包含三个整数 ，表示将序列中 之间的每个数加上 。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 和 。

第二行包含 个整数，表示整数序列。

接下来 行，每行包含三个整数 ，，，表示一个操作。

输出格式

共一行，包含 个整数，表示最终序列。

数据范围

,
,
,
整数序列中元素的值

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

思路分析

差分数组是一种用于高效处理区间更新操作的数据结构。对于一个数组a，我们定义其差分数组d如下：

则有

当我们需要对区间[l, r]进行加法操作时，只需对差分数组进行如下更新：

• d[l] += c
• d[r + 1] -= c
  在进行完所有操作后，我们可以通过前缀和的方式恢复原数组。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

int a[N];
int d[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        d[i] = a[i] - a[i - 1];
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        d[l] += c;
        d[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = a[i - 1] + d[i];
        cout << a[i] << ' ';
    }
}

差分矩阵

题干

输入一个 行 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 ，其中 和 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 。

接下来 行，每行包含 个整数，表示整数矩阵。

接下来 行，每行包含 5 个整数 ，表示一个操作。

输出格式

共 行，每行 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

,
,
,
,
,
矩阵内元素的值

输入样例：

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

思路分析

差分矩阵是差分数组的二维拓展，对于差分矩阵d，我们可以得到以下关系：

由于原矩阵相当于差分矩阵的前缀和矩阵，因此我们可以根据前缀和矩阵的关系得到：

即

当我们需要对原矩阵(x1, y1)到(x2, y2)进行加减操作时，只需对差分矩阵进行如下更新：

• d[x1][y1] += c
• d[x1][y2 + 1] -= c
• d[x2 + 1][y1] -= c
• d[x2 + 1][y2 + 1] += c
  最后通过前缀和的方式恢复原矩阵即可。

初始化差分矩阵时，我们不一定要用上方的公式，我们可以看作对原矩阵每一个点单独进行操作，即对(i, j)到(i, j)的加a[i][j]操作，即

• d[i][j] += a[i][j]
• d[i][j + 1] -= a[i][j]
• d[i + 1][j] -= a[i][j]
• d[i + 1][j + 1] += a[i][j]

由于多次用到这个操作，我们可以写一个add函数来实现。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;

int a[N][N];
int d[N][N];

void add(int x1, int y1, int x2, int y2, int c)
{
    d[x1][y1] += c;
    d[x2 + 1][y1] -= c;
    d[x1][y2 + 1] -= c;
    d[x2 + 1][y2 + 1] += c;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            add(i, j, i, j, a[i][j]);
        }
            
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        add(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j];
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
}

双指针

最长连续不重复子序列

题干

给定一个长度为 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 。

第二行包含 个整数（均在 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

输入样例：

5
1 2 2 3 5

输出样例：

3

思路分析

使用一个数组记录序列，另一个数组记录数字的出现次数。使用双指针i, j维护一个区间，i表示区间的左端点，j表示区间的右端点。初始时i = 1, j = 0，如果a[j + 1]没有出现过并且j < n，则将j右移一位，并将a[j]的出现次数加一，更新答案；否则将a[i]的出现次数减一，并将i右移一位。重复上述过程直到j到达序列末尾。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int a[N];
int cnt[N];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int i = 1, j = 0, res = 0;
	while (j < n)
	{
		while (!cnt[a[j + 1]] && j < n)
		{
			j++;
			cnt[a[j]]++;
		}
		res = max(res, j - i + 1);
		cnt[a[i]]--;
		i++;
	}
	cout << res;
}

数组元素的目标和

题干

给定两个升序排序的有序数组 和 ，以及一个目标值 。

数组下标从 开始。

请你求出满足 的数对 。

数据保证有唯一解。

输入格式

第一行包含三个整数 ，分别表示 的长度， 的长度以及目标值 。

第二行包含 个整数，表示数组 。

第三行包含 个整数，表示数组 。

输出格式

共一行，包含两个整数 和 。

数据范围

数组长度不超过 。
同一数组内元素各不相同。
数组元素

输入样例：

4 5 6
1 2 4 7
3 4 6 8 9

输出样例：

1 1

思路分析

使用指针i指向数组A的开头，指针j指向数组B的结尾。计算A[i] + B[j]的值与目标值x进行比较：

• 如果A[i] + B[j] > x，由于 A[i] 此时是 A 中最小的元素，那么加上 A 中其他的元素只会更大，因此 B[j] 永远不会成为答案，把j左移；
• 如果A[i] + B[j] = x，就找到了答案，输出i和j;
• 如果A[i] + B[j] < x，同理 A[i] 永远不会成为答案，把 i 右移。

时间复杂度为O(n + m)。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

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

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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 (a[i] + b[j] > x) j--;
        if (a[i] + b[j] == x)
        {
            cout << i << ' ' << j << '\n';
            break;
        }
    }
}

判断子序列

题干

给定一个长度为 的整数序列 以及一个长度为 的整数序列 。

请你判断 序列是否为 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 是序列 的一个子序列。

输入格式

第一行包含两个整数 。

第二行包含 个整数，表示 。

第三行包含 个整数，表示 。

输出格式

如果 序列是 序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围

,

输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

思路分析

使用双指针i, j分别指向序列a和b的开头，依次比较a[i]和b[j]的值：

• 如果a[i] == b[j]，说明找到了a[i]在b中的位置，将i和j都右移一位；
• 如果a[i] != b[j]，将j右移一位，继续寻找a[i]在b中的位置。
• 如果i到达了a的末尾，说明a是b的子序列，输出Yes；否则输出No。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;

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

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    
    int i = 1, j = 1;
    while (i <= n && j <= m)
    {
        if (a[i] == b[j])
        {
            i++;
            j++;
        }
        else
            j++;
    }
         
    if (i == n + 1)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';
}

位运算

二进制中1的个数

题干

给定一个长度为 的数列，请你求出数列中每个数的二进制表示中 的个数。

输入格式

第一行包含整数 。

第二行包含 个整数，表示整个数列。

输出格式

共一行，包含 个整数，其中的第 个数表示数列中的第 个数的二进制表示中 的个数。

数据范围

,
数列中元素的值

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

思路分析

要计算一个整数的二进制表示中1的个数，可以直接暴力求解循环32位，也可以使用位运算技巧lowbit，即x & -x，它可以保留x的二进制中最低位的1，其余位均为0，每次将x减去lowbit(x)，直到x变为0，减法操作的次数即为1的个数。

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        int res = 0;
        while (x)
        {
            x -= lowbit(x);
            res++;
        }
        cout << res << ' ';
    }
}

离散化

区间和

题干

假定有一个无限长的数轴，数轴上每个坐标上的数都是 。

现在，我们首先进行 次操作，每次操作将某一位置 上的数加 。

接下来，进行 次询问，每个询问包含两个整数 和 ，你需要求出在区间 之间的所有数的和。

输入格式

第一行包含两个整数 和 。

接下来 行，每行包含两个整数 和 。

再接下来 行，每行包含两个整数 和 。

输出格式

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

数据范围

,
,
,

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

思路分析

由于数轴范围是 级别，因此不可能直接开数组进行处理；而操作与询问次数加起来总共只涉及 个数，我们可以使用离散化的思想，开一个数组记录出现过的数字，然后每次都转成离散化后的下标进行处理；最后区间和使用前缀和思想计算。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int M = 3e5 + 10;

int p[M];
vector<int> X;
PII add[N], que[N];

int findx(int x)
{
    return lower_bound(X.begin(), X.end(), x) - X.begin() + 1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x, c;
        cin >> x >> c;
        X.push_back(x);
        add[i] = {x, c};
    }
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        X.push_back(l), X.push_back(r);
        que[i] = {l, r};
    }
    
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    
    for (int i = 1; i <= n; i++)
        p[findx(add[i].first)] += add[i].second;
    for (int i = 1; i <= X.size(); i++)
        p[i] += p[i - 1];
        
    for (int i = 1; i <= m; i++)
    {
        int l = findx(que[i].first), r = findx(que[i].second);
        cout << p[r] - p[l - 1] << '\n';
    }
}

区间合并

区间合并

题干

给定 个区间 ，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如： 和 可以合并为一个区间 。

输入格式

第一行包含整数 。
接下来 行，每行包含两个整数 和 。

输出格式

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

数据范围

,

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

思路分析

利用贪心思想，先将所有区间按照左端点、右端点双关键字从小到大排序，l和r分别表示当前合并区间的左端点和右端点，ll和rr表示当前遍历到的区间的左端点和右端点，如果ll <= r，说明当前区间与合并区间有交集，将r更新为max(r, rr)；否则将当前合并区间[l, r]存入结果数组中，并将l和r更新为当前区间的端点。最后别忘了将最后一个合并区间存入结果数组中。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 2e9;

PII a[N];
vector<PII> res;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first >> a[i].second;
    
    sort(a + 1, a + 1 + n);
    
    int l = a[1].first, r = a[1].second;
    for (int i = 2; i <= n; i++)
    {
        int ll = a[i].first, rr = a[i].second;
        if (ll <= r)
            r = max(r, rr);
        else
        {
            res.push_back({l, r});
            l = ll, r = rr;
        }
    }
    res.push_back({l, r});
    cout << res.size() << '\n';
}