基础算法

一. 快速排序

应用了分治思想和双指针方法，是一种暴力而优美方法，是不稳定的排序

sort

算法流程：快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

  1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。

  2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

  3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

  4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

排序步骤：

  1. 确定分界点:可以为左端点、右端点、中点或随机点（常用中点）

  2. 调整区间，一分为二：将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。

  3. 递归处理左右两段
    快速排序

注意有许多边界问题，要熟记模板

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 中点
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];
    // (l + r >> 1)使l+r的值右移1位，相当l+r的值除以2取整。
    // i，j为左右两个端点的两侧的指针。注意之所以分别加减1是因为默认会先把指针向中间移动再进行比较，所以这里先移动到左右端点的两侧
    while(i < j) // 一般循环结束时，i == j + 1
    {
        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);
    // 注意当写成quick_sort(q, l , i - 1),quick_sort(q, l, i)，x不能取q[l]（调用左指针时，不取左端点）例如样例为1，2时会陷入死循环
    // 写成quick_sort(q,j + 1, r)时，x 不能取q[r]（调用右指针时，不取右端点）
}

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

AcWing 786. 第k个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 快速排序AcWing 786. 第k个数
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;
int q[N];

void quick_sort(int l, int r)
{
    if(l>=r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    // (l + r >> 1)使l+r的值右移1位，相当l+r的值除以2取整。
    // i，j为左右两个端点的两侧的指针。注意之所以分别加减1是因为默认会先把指针向中间移动再进行比较，所以这里先移动到左右端点的两侧
    while(i < j) // 一般循环结束时，i == j + 1
    {
        do i++ ; while (q[i] < x);
        do j-- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(l, j), quick_sort(j + 1, r);
    // 注意当写成quick_sort(q, l , i - 1),quick_sort(q, l, i)，x不能取q[l]（调用左指针时，不取左端点）例如样例为1，2时会陷入死循环
    // 写成quick_sort(q,j + 1, r)时，x 不能取q[r]（调用右指针时，不取右端点）
}

int main(){
    scanf("%d%d", &n, &k);
    
    for (int i = 0; i < n; ++ i)
        scanf("%d", &q[i]);
        
    quick_sort(0, n-1);
    
    printf("%d\n", q[k-1]);
    return 0;
}

归并排序

基本思想也是分治，分治方法与快排不同，是排序稳定。也使用了双指针算法

归并先递归再操作，快排先操作再递归

归并操作的工作原理如下：第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾

排序步骤：

  1. 确定分界点：以数组的中间为分界点mid=(l+r)/2

  2. 递归分治排序left，right两个部分

  3. 归并——合二为一，两个有序序列从左到右进行一个个比较，大的放入数组

    相等时先放第一个序列中的数，因此归并排序是稳定的

归并排序

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void merge_sort(int q[], int l, int r){
    //递归的终止情况——双指针 l >= r
    if (l >= r) return;
    
    //第一步：分成子问题
    // 求出中点
    int mid = l + r >> 1; // 位运算
    
    //第二步：递归处理子问题
    // 先递归排序两部分
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    
    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1;
    // 利用辅助数组进行排序并归并
    // 辅助数组的左端点为0，而原数组左部分左端点为l，右部分左端点为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]; 
}



AcWing 788. 逆序对的数量

求解逆序对的数量，我们首先理解什么是逆序对，其性质是什么。

经研究可以发现，一个数后面有多少小于它的数，这个数就会有多少逆序对。并且经过排序后，其逆序对个数等于现位置坐标 - 原位置坐标（中间插入的数的个数即为小于它且位于它后面的数的数量）。这是一种先排序再求解的思路，为了同时存储现位置和原位置，需要用到pair。

现在，让我们思考一下能否在排序的同时记录数量，这就减少了复杂度。只要我们能在一个较小数重排到较大数的前面时加1即可。这种思路显然必须要选择一种相对前后位置只发生一次变化的排序方法（避免重复记录）。这时候我们可以考虑归并排序。

归并排序是一种及其特殊的排序方法。其排序方法是递归的，且边界情况是两个相邻项的排序，这种思想和许多dp问题都是不谋而合的。相邻项一旦排好，其相对前后位置便在后续递归中不再变化。因而我们可以使用归并排序，并在排序的同时记录个数。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 归并排序——AcWing 788. 逆序对的数量
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N =100010;

int n;
int q[N];
int tmp[N];

LL merge_sort(int l ,int r){
    if (l >= r) return 0;
    int mid = l + r >> 1; // 位运算
    // 求出中点
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    // 加上下层递归求得的逆序对个数
    // 先递归排序两部分
    int k = 0, i = l, j = mid + 1;
    // 利用辅助数组进行排序并归并
    // 辅助数组的左端点为0，而原数组左部分左端点为l，右部分左端点为mid + 1
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        // 为了保持稳定，遇到相同值时先放左半部分的
        else{
            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(){
    scanf("%d", &n);
    for (int i = 0; i< n; ++ i)
        scanf("%d", &q[i]);
 
    printf("%lld\n", merge_sort(0, n - 1));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 归并排序——AcWing 788. 逆序对的数量
// 另一种写法
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N =100010;

int n;
int q[N];
int tmp[N];

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

int main(){
    scanf("%d", &n);
    for (int i = 0; i< n; ++ i)
        scanf("%d", &q[i]);
 
    printf("%lld\n", merge_sort(0, n - 1));
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 归并排序——AcWing 788. 逆序对的数量
def main():
    def merge_sort(l, r):
        # 区间内元素个数小于两个
        if l >= r:
            return
        
        # 找区间中点
        mid = l + r >> 1

        # 2.递归分治
        merge_sort(l, mid)
        merge_sort(mid + 1, r)
        
        # 3. 归并
        k, i, j = 0, l, mid + 1
        while i <= mid and j <= r:
            if q[i] <= q[j]:
                tmp[k] = q[i]
                i += 1
            else:
                tmp[k] = q[j]
                j += 1
            k += 1
        
        # while i <= mid:
        #     tmp[k] = q[i]
        #     i += 1
        #     k += 1

        # while j <= r:
        #     tmp[k] = q[j]
        #     j += 1
        #     k += 1
        
        # 直接使用切片
        if i <= mid or j <= r:
            st, cnt = (i, mid - i + 1) if i <= mid else (j, r - j + 1)
            tmp[k:k + cnt] = q[st:st + cnt]
        
        # 赋值回原数组
        # 直接使用切片
        # q[l:r + 1] = tmp[:k] # 注意k最后会加1，所以切片时不是k+1
        q[l:r + 1] = tmp[:r - l + 1]
        
    n = int(input())
    q = list(map(int, input().split()))
    tmp = [0] * n
    merge_sort(0, n - 1)
    print(' '.join(map(str, q)))
    
if __name__ == "__main__":
    main()

二分

有单调性一定可以二分，可以二分的题目不一定必须单调

二分的本质是，根据某一性质将区间左右一分为二，使一部分满足该性质，另一部分不满足该性质。

如果可以找到一个性质使区间左右一分为二（一部分满足，一部分不满足），二分就可以找到性质的边界。

二分问题要满足的条件：

  1. 确定一个区间，使得目标值一定在区间中

  2. 找一个性质，满足：

    • 性质具有二段性
    • 答案是二段性的分界点

二分问题一定满足1，95%满足2。

整数二分

整数二分时根据性质分成的两部分没有交集。

分为两类：分界点在左半部分或分界点在右半部分。

二分时，根据性质将区间一分为二，每次选择答案所在区间进行进一步处理。区间长度为一时即为答案。

当分界点在左半部分时，之所以$ mid = \frac{l+r+1}{2} $多加一个1是为了避免mid = l导致更新时l = mid会不发生变化，陷入死循环（这种情况出现在l = r - 1时）。话句话说，保证区间为2时mid取右侧而不是左侧。（分界点在左侧）

最后l和r是一定相等的,但是mid不一定等于l，可能是mid-1等于l。二段性的分界点就是答案说的就是最终l等于r。l和r维护一个区间，对于整数二分，当区间长度为1时，就是分界点。

二分的一大作用：求上界函数和下界函数QQ图片20230304222111

整数二分步骤：

  1. 找一个区间[L, R]，使得答案一定在该区间中

  2. 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点

  3. 分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案再哪个区间

    • 如果条件成立（性质满足）的区间在左部，则为<= x型，采用L=mid模板
    • 如果条件成立（性质满足）的区间在右部，则为<= x型，采用R=mid模板

  4. 如果更新方式写的是R = mid，则不用做任何处理；如果更新方式写的是L = mid，则需要在计算mid时加上1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 性质判断
bool check(int x){}

// 右半部分满足性质，如大于等于x的数
int bsearch_1(int l, int r){
    while (l < r){ // 区间长度大于等于1
        // 分界点在右半部分，如大于等于某个数的最小值
        int mid = l + r >> 1;
        //int mid = l + (r - l) / 2; // 避免溢出问题
        if (check(mid)) r = mid;
        // 成立时，对右端点更新且包含mid(分界点在成立区间得左端)
        else l = mid + 1;
    }
    return l;
    // 最终l==r，l和r都是答案，但mid不一定是答案
}

// 左半部分满足性质，如小于等于x的数
int bsearch_2(int l, int r){
    while (l < r)
    {
        // 分界点在左半部分，如小于等于某个数的最大值
        int mid = l + r + 1 >> 1;
        //int mid = l + (r - l + 1) / 2; // 避免溢出问题
        // 当分界点在左半部分时，之所以$mid = \frac{l+r+1}{2}$多加一个1是为了避免mid = l导致更新时l = mid会不发生变化，陷入死循环（这种情况出现在l = r - 1时）。
        if (check(mid)) l = mid;
        // 成立时，对左端点更新且包含mid(分界点在成立区间得右端)
        else r = mid - 1;
        // 不成立时，对右端点更新，且不包含mid
    }
    return l;
    // 最终l==r，l和r都是答案，但mid不一定是答案
}

AcWing 789. 数的范围

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 整数二分——AcWing 789. 数的范围
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1000010;

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

int bsearch_1(int l, int r, int k){
    while (l < r) // 区间长度大于等于1
    {
        // 分界点在右半部分
        int mid = l + r >> 1;
        if (q[mid] >= k) r = mid;
        // 成立时，对右端点更新且包含mid(分界点在成立区间得左端)
        else l = mid + 1;
    }
    return l;
    // 最终l==r
}
int bsearch_2(int l, int r, int k){
    while (l < r)
    {
        // 分界点在左半部分
        int mid = l + r + 1 >> 1;
        // 当分界点在左半部分时，之所以$mid = \frac{l+r+1}{2}$多加一个1是为了避免mid = l导致更新时l = mid会不发生变化，陷入死循环（这种情况出现在l = r - 1时）。
        if (q[mid] <= k) l = mid;
        // 成立时，对左端点更新且包含mid(分界点在成立区间得右端)
        else r = mid - 1;
        // 不成立时，对右端点更新，且不包含mid
    }
    return l;
    // 最终l==r
}

int main(){
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < n; ++ i)
        scanf("%d", &q[i]);
        
    while (m--){
        scanf("%d", &k);
        // 求k的起始位置，利用 x >= k的性质二分
        int a = bsearch_1(0, n-1, k);
        // 注意判断是否存在的方法——如果边界值不等于k，说明数组中不存在k
        if (q[a] != k) puts("-1 -1");
        else {
            int b = bsearch_2(0, n-1, k);
            // 求k的终止位置，利用 x <= k的性质二分
            printf("%d %d\n", a, b);
        }
    }
    return 0;
}
Python

手写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 整数二分——AcWing 789. 数的范围
def main():
    def lower_bound(l, r):
        while l < r:
            mid = l + r >> 1
            if q[mid] >= k: r = mid
            else: l = mid + 1
        return l
        
    def upper_bound(l ,r):
        while l < r:
            mid = l + r + 1 >> 1
            if q[mid] <= k: l = mid
            else: r = mid - 1
        return l
        
    n, m = map(int, input().split())
    q = list(map(int, input().split()))
    for _ in range(m):
        k = int(input())
        l = lower_bound(0, n - 1)
        if q[l] != k:
            print("-1 -1")
        else:
            r = upper_bound(0, n - 1)
            print(l, r)
            
if __name__ ==  "__main__":
    main()

使用bisect库，速度略慢点

bisect.bisect和bisect.bisect_right返回大于x的第一个下标(相当于C++中的upper_bound)

bisect.bisect_left返回大于等于x的最左侧第一个下标

当x存在多个时，bisect_left返回最左边的x的索引bisect_right返回最右边的x的索引加1；如果元素不存在，则返回将其插入到何处
eg: l = [1, 4, 5]，bisect_left(l, 4)返回1，bisect_left(l, 2)返回1，bisect_left(l, 6)返回3

因为bisect返回大于x的最左的第一个下标，所以其减一即得到小于等于x的最右侧的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 整数二分——AcWing 789. 数的范围
from bisect import bisect, bisect_left
def main():
    n, m = map(int, input().split())
    q = list(map(int, input().split()))
    for _ in range(m):
        k = int(input())
        l = bisect_left(q, k)
        # 这里需要注意，如果元素不存在，则返回将其插入到何处，因而返回值可能越界（插在最后一个元素后面），需要特判
        if l >= n or q[l] != k: 
            print("-1 -1")
        else:
            r = bisect(q, k) - 1
            print(l, r)
            
if __name__ ==  "__main__":
    main()

实数/浮点数二分

二分时，根据二段性性质将区间一分为二，每次选择答案所在区间进行进一步处理。浮点数二分没有整除问题，每次区间严格缩小一半，因而比较容易写。但由于区间长度可以无限小，一般无法求出精确的分界点。通常区间长度为足够小时（规定一个精度）即为答案。一般取得精度要求的答案小两位。或者规定迭代次数，迭代到规定次数即为答案（每循环一次区间长度缩小二分之一）。

模板

1
2
3
4
5
6
7
8
9
10
11
bool check(double x){}
double bsearch_3(double l, double r){
    const double eps = 1e-6;  
    //精度一般比要求保留的位数大2就可以
    while (r - l > eps){ // 区间长度大于精度
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

AcWing 790. 数的三次方根

三次方根具有单调性，因而可以直接使用二分法求解。要求精度是6位，相当于数据数量级在$ 10^{10} $ ，而$n <= n^{18} $时都可以使用$O(logn)$的二分算法。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 浮点数二分——AcWing 790. 数的三次方根
#include <iostream>
#include <algorithm>

using namespace std;

const double eps = 1e-8;
//精度一般比要求保留的位数大2就可以

int main(){
    double x;
    scanf("%lf", &x);
    
    double l = -100, r = 100;
    // 根据数据范围确定解的区间范围
    
    while (r - l > eps)// 区间长度大于精度即可返回
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        // 使用二分法求解三次方根
        else l = mid;
    }
    printf("%.6lf", l);
    return 0;
}
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 浮点数二分——AcWing 790. 数的三次方根
def main():
    l, r = -100, 100
    x = float(input())
    
    eps = 1e-8
    while r - l > eps:
        mid = (l + r ) / 2
        if mid ** 3 >= x:
            r = mid 
        else:
            l = mid 
    
    print("%.6f" % l)
    
if __name__ == "__main__":
    main()

高精度加法

AcWing 791. 高精度加法

为了便于进位，要把数在数组中倒置存储（个位存最前面），因为在数组的末尾补数更容易。

每一位单独进行运算并处理进位问题

减法要处理借位问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);
    // 位数多的放前面

    vector<int> C;

    int t = 0; // t用于表示进位

    for (int i = 0; i < A.size(); ++ i){
        t += A[i];
        if (i < B.size()) t += B[i]; 
        // 注意判断较小数的位数
        // 加上当前位的数值
        C.push_back(t % 10);
        t /= 10; // 求出进位
    }
    if (t) C.push_back(t);
    // 最后的进位单独处理
    return C;
}

vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;

    int t = 0; 
    
    for (int i = 0; i < A.size(); ++ i){
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}


vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;

    for (int i = 0; i < A.size(); ++ i){
        t += A[i];
        if (i <B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}


AcWing 791. 高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 高精度加法——不压位——AcWing 791. 高精度加法
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B){
    if (A.size() < B.size()) return add(B, A);
    // 位数多的放前面

    vector<int> C;

    int t = 0; // t用于表示进位

    for (int i = 0; i < A.size(); ++ i){
        t += A[i];
        if (i < B.size()) t += B[i]; 
        // 注意判断较小数的位数
        // 加上当前位的数值
        C.push_back(t % 10);
        t /= 10; // 求出进位
    }
    if (t) C.push_back(t);
    // 最后的进位单独处理
    return C;
}

int main(){
    string a, b;
    vector<int> A, B;
    
    cin >> a >> b;
    // 不建议使用scanf 输入string类型字符串
    // 如果使用scanf，必须要为string提前分配足够空间
    
    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) printf("%d", C[i]);
    puts("");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 高精度加法——压九位——AcWing 791. 高精度加法
#include <iostream>
#include <vector>

using namespace std;

const int base = 1000000000;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % base);
        t /= base;
    }

    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, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (a[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            A.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (b[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            B.push_back(s);
            s = j = 0;
            t = 1;
        }
    }

    auto C = add(A, B);

    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
    cout << endl;

    return 0;
}


##高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    for (int i = 0, t = 0;i < A.size(); ++ i){
        // t表示借位
        t = A[i] - t;
        // 先减去借位
        if (i < B.size()) t -= B[i];
        // 注意判断较小数的位数
        C.push_back((t + 10) % 10);
        // (a + r) % r得到的余数一定是正余数
        if (t < 0) t = 1;
        // t < 0说明借位了，借位一定是借了1
        else t = 0;
        // 没借位则t为0
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    // 注意需要处理前导零的问题（这里高位在后，前导零也在最后），但当只有一位是0必须保留
    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;
        if (i < B.size()) t -= B[i];
        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;
}

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;
        if (i < B.size()) t -= B[i];
        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;
}



AcWing 792. 高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 高精度减法——AcWing 792. 高精度减法
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// 判断A和B的大小关系，A更大返回true，B更大返回false
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;
}


// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;

    for (int i = 0, t = 0; i < A.size(); ++ i){
        // t表示借位

        t = A[i] - t; // 先减去借位
        if (i < B.size()) t -= B[i]; // 注意判断较小数的位数

        C.push_back((t + 10) % 10);
        // (a + r) % r得到的余数一定是正余数

        if (t < 0) t = 1;
        // t < 0说明借位了，借位一定是借了1

        else t = 0; // 没借位则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;
    // 不建议使用scanf 输入string类型字符串
    // 如果使用scanf，必须要为string提前分配足够空间
    
    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');
    
    vector<int> 
    C;    
    // 判断A和B的大小关系，默认A更大
    if (cmp(A,B)) C = sub(A, B);
    else{
        printf("-"); // 小减大，先输出负号，然后当作大减小处理
        // 别错用成puts("-")，会多换行
        C = sub(B, A);
    }

    for (int i = C.size() - 1; i >= 0; -- i) printf("%d", C[i]);
    puts("");
    return 0;
}



高精度乘低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0; // t 用来表示进位
    for (int i = 0; i < A.size() || t; ++ i){
        // 注意把最后处理进位的问题合并到了一起，只要t不为0最后就会执行下去
        if (i < A.size()) t += A[i] * b; 
        // 注意这里是高精度乘低精度，所以直接用低精度数乘以每一位即可
        C.push_back(t % 10);
        t /= 10; // 求出进位 
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    // 注意需要处理前导零的问题（这里高位在后，前导零也在最后），但当只有一位是0必须保留
    // 之所以会产生前导零
    return 0;  
}

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

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return 0;
}


AcWing 793. 高精度乘法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 高精度乘低精度——AcWing 793. 高精度乘法 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0; // t 用来表示进位
    for (int i = 0; i < A.size() || t; ++ i){
        // 注意把最后处理进位的问题合并到了一起，只要t不为0最后就会执行下去
        if (i < A.size()) t += A[i] * b; 
        // 注意这里是高精度乘低精度，所以直接用低精度数乘以每一位即可
        C.push_back(t % 10);
        t /= 10; // 求出进位 
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();;
    // 注意需要处理前导零的问题（这里高位在后，前导零也在最后），但当只有一位是0必须保留
    // 之所以会产生前导零
    return C;  
}

int main(){
    string a;
    int b;
    vector<int> A;
    
    cin >> a >> b;
    // 不建议使用scanf 输入string类型字符串
    // 如果使用scanf，必须要为string提前分配足够空间
    
    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) printf("%d", C[i]);
    puts("");
    return 0;
}




高精度除以低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    r = 0; // r为除法的余数
    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();
    // 处理前导0的问题
    return C;
}


AcWing 794. 高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 高精度除以低精度——AcWing 794. 高精度除法   
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    r = 0; // r为除法的余数
    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();
    // 处理前导0的问题
    return C;
}

int main(){
    string a;
    int b, r;
    vector<int> A;
    
    cin >> a >> b;
    // 不建议使用scanf 输入string类型字符串
    // 如果使用scanf，必须要为string提前分配足够空间
    
    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) printf("%d", C[i]);
    printf("\n%d\n", r);
    return 0;
}

前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。作用是快速求出任意区间的和。前缀和可以在O(n)时间统计和修改，在O(1)时间内查询统计任意区间之和；

前缀和下标一般从1开始，方便将前缀和作为任意区间和的特殊情况，不需要额外处理。

前缀和是一种空间换时间的思想

定义式 递推式
一维前缀和 $S[i] = \sum\limits_{j=0}^{i}a[j]$ $S[i] = S[i-1] + a[i]$
二维前缀和 $S[x][y] = \sum\limits_{i=0}{x}\sum\limits_{j=0}{y}a[i][j]$ $S[x][y] = S[x-1][y] + S[x][y-1] - S[x-1][y-1] + a[x][y]$

一维前缀和

一维前缀和数组:$$S_i = a_1 + a_2 + \cdots + a_i，边界S_0 = 0$$

作用：可以通过一次运算求解原数组任意区间内所有数的和（区间长度位1时即为每个元素的值）
$$
\sum\limits_{i=l}^r a_i = S_r - S_l
$$

如果使用暴力解法，每次都遍历一遍给出的区间，计算出答案，这样时间复杂度会达到$O(n*m)$，极有可能会 TLE。

使用前缀和来做的话，能将时间复杂度降到$O(n+m)$，极大地减少了时间。

前缀和数组的第$i$项就是一个序列前面$i$个数的总和，求法如下：

1
2
3
4
5
6
void init()
{
    s[0] = 0; // 边界条件
    for(int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
}

对于已经求出的前缀和，区间$[L,R]$的和即为$res = s[r] - s[l - 1]$

1
2
3
4
int get(int l, int r)
{
    return s[r] - s[l - 1];
}

AcWing 795. 前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 前缀和——AcWing 795. 前缀和
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

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

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

    for (int i = 1; i <= n; ++ i) s[i] = s[i - 1] + a[i];
    // 前缀和的初始化，本质是利用前缀和的递推式和差分数组来求前缀和

/*
    // 读取数据和初始化可整合在一起
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
*/

    while (m --){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); 
        // 区间和的计算
    }
    return 0;
}

二维前缀和：

快速求出任意子矩阵的所有元素的和。求解利用了容斥原理。

a[i][j]表示第i行j列的元素S[i][j]为a[i][j]左上角子矩阵的所有元素的和

以(1, 1)为左上角，(x, y)为右下角的子矩阵的和为：
$$
S[x][y] = S[x-1][y] + S[x][y-1] - S[x-1][y-1] + a[x][y]
$$

1
2
3
4
5
6
// 预处理，求以(i,j)为右下角、(1,1)为左上角的矩阵中的元素和
int init(){
    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];
}

当给出$x_1, y_1, x_2, y_2$时，要查询的子矩阵的和即为
$$
res = s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1] + s[x_1 - 1][y_1 - 1]
$$

1
2
3
int get(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

AcWing 796. 子矩阵的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 二维前缀和——AcWing 796. 子矩阵的和
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main(){
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            scanf("%d", &s[i][j]);

    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];
            // 前缀和的初始化，本质是利用前缀和的递推式和差分数组来求前缀和

/*
    // 读取数据和初始化可整合在一起
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j){
            scanf("%d", &s[i][j]);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i-1][j-1];
        }
*/

    while (q --){
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        // 区间和的计算, 类似容斥原理
    }
    return 0;
}

AcWing 1230. K倍区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// AcWing 1230. K倍区间
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N], cnt[N];

int main(){
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ){
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL res = 0;
    cnt[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        int t = s[i] % k
        res += cnt[t] ++;
        // 利用同余性质:(a - b) % p = (a % p - b % p ) % p可以发现
        // (S[r] - S[l]) % k == (S[r] % k - S[l] % k) % k
        // 又S[r] % k < k, S[l] % k < k必得出结论：
        // S[r]与S[l]要同余
        // 结果中不用求解排列组合，而是利用每次循环，每多一个元素就增加原先元素数个K倍区间

        // if (t == 0) res ++;
    }

    printf("%lld\n", res);

    return 0;
}


差分

前缀和与差分是逆运算。差分可看作前缀和的“逆运算”，可在O(1)时间操作任意区间；

已知原数组$a_1, a_2, a_3,\cdots,a_n$，构造数组$b_1,b_2,\cdots,b_n$，使得$a_i= b_1 + b_2 + b_i$，则a数组是b数组得前缀和，b数组是a数组的差分。差分数组可以将对a数组任意区间加减同一值的操作优化到$O(1)$。

一维差分

一维差分可以快速地实现如下两个操作：

1. 区间修改（给原数组任意连续区间加减固定值），时间复杂度为$O(1)$

假如现在要将原数列$a[]$区间$[L, R]$ 上的每个数都加上 $c$，那么通过上述定义可以知道：

  • 第一个受影响的差分数组中的元素为$b[L]$，所以令$b[L] +=c$，那么后面数列元素在计算过程中都会加上c。最后一个受影响的差分数组中的元素为$b[R]$，所以令$b[R+1]-=c$，那么可以保证不会影响到R之后数列元素的计算。这样一来，就不必对区间内每一个数进行处理，只需处理两个端点即可。

1
2
3
4
5
// 给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
void insert(int L, int R, int x){
    b[L] += x;
    b[R + 1] -= x;
}

2. 查询单点(求前缀和)，时间复杂度为$O(n)$

这一操作其实就是求解前缀和的过程：我们利用差分数组和前缀和的递推关系来求解前缀和。

根据上述定义，差分数组$b[i]$的前缀和就是原序列$a[i]$的值。

1
2
3
4
void get(){
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + b[i];
}

如何构造差分数组？

初始化：不需要过分关注差分数组b是怎么构造出来的，只需要知道差分与前缀和是互逆运算即可。事实上，根本就不需要去构造差分数组b。

一开始可以把原数组$a$想象成全是0，即$a=[{0,0,\cdots,0}]$，此时相应的差分数组$b$也全是0， 即$b=[{0,0,\cdots,0}]$，接下来，对原数组$a$的初始值可以作如下考虑：

  • $a[1]$相当于区间 $[1,1]$ 的每个数都加上$a[1]$

  • $a[2]$相当于区间 $[2,2]$ 的每个数都加上$a[n]$
    …

  • $a[n]$相当于区间 $[n,n]$ 的每个数都加上$a[n]$

即我们把原数组也当作是差分出来的。这样，用上面的区间修改操作$insert()$即可完成赋初始值，构造出差分数组。

AcWing 797. 差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 一维差分——AcWing 797. 差分
#include <iostream>

using namespace std;

const int N = 100010;

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

void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main(){
    scanf("%d%d", &n, &m);

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

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

    while (m --){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l ,r, c);
        // 区间操作，给原数组任意连续区间加减固定值
    }

    for (int i = 1; i <= n; ++ i) b[i] += b[i -1];
    // 求前缀和

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 一维差分——AcWing 797. 差分
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

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

void insert(int l, int  r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main(){
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        insert(i, i, a[i]);
        // 求差分数组
    }
    
    while (m --){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
        // 区间操作，给原数组任意连续区间加减固定值
    }
    
    // 求前缀和
    for (int i = 1; i <= n ; ++ i) {
        b[i] += b[i - 1];
        printf("%d ", b[i]);
    }
    puts("");
    
    return 0;
}

二维差分

定义：假设有原数组 $a[][]$，现构造出一个数组 $b[][]$，使得 $a[i][j]$ 等于 $b[i][j]$ 格子左上部分所有元素的和，那么 $b[][]$ 就称为 $a[][]$ 的差分，$a[][]$ 就称为$b[][]$的前缀和。可以发现，差分与前缀和是逆运算。

类比于一维差分，二维差分同样可以快速地实现如下两个操作：

1.将原数组$a[][]$ 的以$(x_1, y_1)$ 为左上角、$(x_2, y_2)$为右下角的矩形区域里的每个数都加上$c$。

$$ b[x_1, y_1] += c,\ b[x_2 + 1, y_1] -= c,$$$$ b[x_1, y_2 + 1] -= c,\ b[x_2 + 1, y_2 + 1] += c $$

1
2
3
4
5
6
7
8
9
10
// 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c
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;
}


2.查询单点，差分数组$b[i][j]$前缀和就是原数组 $a[i][j]$ 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 求以(i,j)为右下角、(1,1)为左上角的矩阵中的元素和
void get()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] +
             b[i][j];
}

void get(){
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + b[i][j];
}

同理，不需要过分关注二维差分数组 $b[][]$是如何构造出来的，仅仅依靠上面的 $insert()$ 操作即可完成赋初值。

AcWing 798. 差分矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 二维差分——AcWing 798. 差分矩阵
#include <iostream>
#include <algorithm>

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(){
    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(i, j, i, j, a[i][j]);
            // 求差分数组
    
    while (q --){
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
        // 子矩阵操作，给原数组任意子矩阵加减固定值
    }

    // 求前缀和
    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) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 二维差分——AcWing 798. 差分矩阵
#include <iostream>
#include <algorithm>

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(){
    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]);
            insert(i, j, i, j, a[i][j]);
            // 求差分数组
        }
    
    while (q --){
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
        // 子矩阵操作，给原数组任意子矩阵加减固定值
    }
    
    // 求前缀和并输出
    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];
            printf("%d ", b[i][j]);
        }
        puts("");
    }
    return 0;
}

打表法

打表，通俗理解就是“预处理”的意思，把所有可能的情况都求出来，你要哪一个我直接查表，把表中的结果给你。

在程序中一次性计算出所有用到的结果，之后的查询直接取这些结果。

具体的，我们可以创建一个 静态数据结构 来存储打表信息（需确保全局唯一，即使存在多组测试数据只生成一次打表数据）。

如果打表逻辑计算量接近 [公式] 上限，可以考虑放到本地去做，这里数据量较少，直接放到 static 代码块去做即可。

模拟法和打表法，经常会同时出现，因为打表就要按照题目的意思去模拟。

AcWing 3646. 分水果

1
2
3
4
// AcWing 3646. 分水果



双指针算法

一般分为两类

  1. 对于一个序列，用两个指针指向同一序列的两端，用于维护一段区间

  2. 对于两个序列，两个指针分别指向两个序列，用于维护某种次序，比如归并排序中合并两个有序序列的操作

  3. 常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

模板

1
2
3
4
5
6
7
8
9
for (int i = 0, j = 0; i < n; i ++ ){
    // i、j起始位置不固定

    while (j < i && check(i, j)) j ++ ; // 对j进行更新
    // j < i象征性表示要判断j是否满足范围限制
    // check()指满足某种性质

    // 下面写具体问题的逻辑
}

核心思想：双指针算法的最核心用途是进行优化，将暴力枚举的双重循环做法优化到单循环。复杂度由$O(n^2)$优化到$O(n)$。

优化的关键在于需要用到一些特殊的性质，如单调性等。
i和j的单调关系可以类似于i每次增加时，j也不会减小

求解时可以首先写出双重循环的暴力算法，然后研究问题，利用性质进行优化。

和动态规划一样，在双指针中i，j表示的具体含义也是一个要思考的关键点（注意i，j表示的状态不一定同类）。

虽然双指针算法看上去是两重循环，但实质上两个指针都只会遍历一次，总复杂度是$O(2n)$

有些双指针也可以理解成一个指针+一个标记

image-20230328230115557

AcWing 799. 最长连续不重复子序列

使用双指针算法时可以首先实现暴力算法，然后再研究性质进行优化，思考双重循环的指针i和j之间的关系与性质。

这里进行优化的核心性质是j随i的增大也单调递增，利用这种单调性可以使用双指针算法进行优化，将复杂度由$O(n^2)$优化到$O(n)$。

这本质是利用i和j来维护状态，且利用了当前状态和前面状态的相关性进行优化，每个状态都对印古从j到i的区间，j和i都不会回溯只会增大。

本题的动态统计区间内元素数的技巧——哈希判重要熟记，使用数组s[i]动态维护每个区间中个元素个数，s[a[i]]表示a[i]这个数出现的次数，类似于哈希。进入区间时对应元素s[i]++，离开区间时对应元素s[i]–。数据过大时，可以用哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// AcWing 799. 最长连续不重复子序列
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;

const int N = 100010;

int n;
int q[N], s[N];
// s[]用于动态统计区间内元素数
int res;

int main(){
    scanf("%d", &n);
    
    for (int i = 0; i < n; ++ i)
        scanf("%d", &q[i]);
    
    // 双指针算法
    // 
    // i和j的大小满足单调关系
    for (int i = 0, j = 0; i < n; ++ i){
        s[q[i]] ++;
        while (j < i && s[q[i]] > 1) s[q[j ++]] --;
        res = max(res, i - j + 1);
    }
    
    printf("%d\n", res);
    return 0;
}

位运算

  1. 求n的二进制表示中第k位是几：n >> k && 1
    先把第k位移到最后一位(n >> k)，然后取出最后一位( n >> k && 1)

  2. lowbit(x)操作，返回x最右端一位的1(最后一位1）所代表的大小x & -x
    负数的补码是原码取反加1x & -x == x & (~x + 1)。已知其补码相对于原码，最右端的1和其右面的0是不变的，其余全部取反，因而x & -x后只剩下最右端的1了，其余全变成0。这是树状数组的一个基本操作。

    用途之一是可以用来求一个数x二进制表示中1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 统计x二进制表示中1的个数
#include <iostream>

using namepace std;

// 返回x最右端一位的1所代表的大小
int lowbit(x){
    return x & -x;
}

int main(){
    int n;
    scanf("%d", &n)
    while (n --){
        int x;
        scanf("%d", &x);
        int res = 0;
        while (x != 0){
            x -= lowbit(x);
            // 每次减去x的最后一个1所代表的数值
            ++ res;
        }
        printf("%d\n", res);
    }
    return 0;
}

离散化

这里特指整数的离散化，且不改变顺序（保序）。把原来的数字，用它们的相对大小来替换原来的数值，而相对顺序仍然不变。

数据的值域范围比较大，但个数比较少，非常稀疏。此时如何存储？需映射到从0开始得自然数。

离散化的两个问题：

  • 去重：可能有重复元素，需要去重，可使用库函数。

  • 快速映射：需要能够快速算出离散化后的值，使用二分来查找

要求求解的量与绝对位置无关

映射到对应下标

注意所有用到的数都要存进去。要开30000，插入和查询的位置都要存进去。

把数字看成数组下标，却只考虑相对大小关系

离散化经常用于树状数组或权值线段树

模板

C++

去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}

Python

不去重，重复数字离散化后不一样

1
2
3
4
5
b = sorted(a)
for i range(len(b)):
    a[a.index(b[i])] = i + 1 # 由于从1开始映射，需加1
    # a.index(x)查找x在a中位置，从列表中获取指定索引元素的第一个匹配位置
    # 由于a会被更新，前面重复的都被变成了相对位置，就避免了查找位置不变的问题

去重写法，重复数字离散化后一样

1
2
3
4
b = list(set(a)) # 利用集合去重
b.sort()
for i in range(len(a)):
    a[i] = b.index(a[i]) + 1 # 为保持一致，就要查找不被改变的b，由于b的index就对应于相对大小顺序，所以直接加1

区间合并

将有交集的区间合并

维护与更新

为了便于维护和更新，迭代顺序很重要——需要先按照左端点大小排序。

区间贪心也是类似思路。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 将所有存在交集的区间合并
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;
}