一维差分

b为a的差分，a为b的前缀和。\(b_1 = a_1\) , \(b_n = a_n - a_{n-1}\)

前缀和转差分

假想前缀和全为0，此时差分全为0。然后模拟插入，即前缀和 [1,1] 元素加上 \(a_1\)，[2,2] 元素加上 \(a_2\)，[n,n] 元素加上 \(a_n\)

797

797. 差分 - AcWing题库

由 b 数组（差分）得到 a 数组（前缀和）O(n)

给 [L,R] 每个数加上 c，每次操作暴力方法 O(n)，使用差分 O(1)

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], b[N];

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

int main() {
    int n, m;
    cin >> 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]);
    }
    int l, r, c;
    while (m--) {
        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++) cout << b[i] << " ";
    return 0;
}

二维差分

构造 \(b_{ij}\) 满足 \(a_{ij} = \sum_{1}^{n}\sum_{1}^{m}b_{ij}\)

子矩阵全加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\)

前缀和转差分

假想前缀和全为0，此时差分全为0。然后模拟插入，即模拟子矩阵 [1 , 1][1 , 1] 加 c

798

798. 差分矩阵 - AcWing题库

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

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

void insert(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;
    cin >> 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, x2, y1, y2, c;
        cin >> 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][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;
}

双指针算法

用于把朴素算法优化到 O(n)

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

第一类双指针

指向两个序列，用两个指针维护一段区间

第二类双指针

指向一个序列，如快排。维护某种次序，比如归并排序中合并两个有序序列的操作

799 ?? 第一类

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

数据量 1e5 ，用数组统计出现次数。当数据量很大时用哈希表做

从朴素算法看 i，j 的单调关系，然后套用双指针。两个指针 [i,j] 维护一个最长不重复序列区间。i，j 一定是往右走的（单调性），若 i 往左走则与最长不重复序列区间矛盾。

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int count = 0;
    for (int i = 0, j = 0; j < n; j++) {
        b[a[j]]++;
        while (b[a[j]] > 1) {
            b[a[i]]--;
            i++;
        }
        count = max(j - i + 1, count);
    }
    cout << count;
    return 0;
}

800 第二类

800. 数组元素的目标和 - AcWing题库