Day 15 · 前缀和与差分

题意：有 n 个学生的初始成绩。老师要做 p 次操作，每次把第 x 个到第 y 个学生每人加上 z 分。所有操作做完后，输出全班的最低分。

思路

看着像「区间修改 + 最后问最小值」，这正是差分的标准场景。

1. 把初始成绩装进差分数组。本题最省内存的写法是：读入 a[1..n] 之后，原地把 a 变成差分数组 —— 从后往前做 a[i] -= a[i-1]（从后往前是因为 a[i-1] 这时还没被覆盖，仍是原值）。
2. 处理 p 次操作：每次读 x、y、z，做 a[x] += z; a[y+1] -= z;。
3. 求前缀和还原 + 取最小值：一边累加一边更新答案，不用另外开数组。

整体复杂度 O(n + p)，全部是线性操作。内存上 a 数组开 5000005 个 int，约 20 MB，够用。

3 2
1 1 1
1 2 1
2 3 1

2

过程：[1,2] 加 1 后是 2 2 1；再 [2,3] 加 1 后是 2 3 2。最低分 2。

完整代码

#include <cstdio>

const int MAXN = 5000005;
int a[MAXN];                       // 原地当差分数组用

// -------- 快读：一次读 1MB 进缓冲区，再逐字符取，比 cin / scanf 快得多 --------
namespace FastIO {
    const int BUFSIZE = 1 << 20;   // 1 MB 缓冲区
    char buf[BUFSIZE];
    int len = 0, pos = 0;

    inline char getChar() {
        if (pos == len) {                  // 缓冲区读完了，再补一锅
            len = (int)fread(buf, 1, BUFSIZE, stdin);
            pos = 0;
            if (len == 0) return 0;        // 文件结束
        }
        return buf[pos++];
    }

    inline int readInt() {
        char ch = getChar();
        while (ch < '0' || ch > '9') {     // 跳过空格、换行
            if (ch == '-') {               // 支持负数（保险起见）
                ch = getChar();
                int x = 0;
                while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getChar(); }
                return -x;
            }
            if (ch == 0) return 0;
            ch = getChar();
        }
        int x = 0;
        while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getChar(); }
        return x;
    }
}
using FastIO::readInt;

int main() {
    int n = readInt(), p = readInt();
    for (int i = 1; i <= n; i++) a[i] = readInt();

    // 把 a 就地变成差分数组：d[i] = a[i] - a[i-1]
    // 从后往前做，因为 a[i-1] 还是原来的值，没被覆盖
    for (int i = n; i >= 2; i--) a[i] -= a[i - 1];

    // p 次区间加：区间 [x, y] 全体 +z  ->  d[x] += z, d[y+1] -= z
    for (int i = 0; i < p; i++) {
        int x = readInt(), y = readInt(), z = readInt();
        a[x] += z;
        a[y + 1] -= z;                 // y == n 时改的是 n+1 号位，数组多开过，安全
    }

    // 对差分数组求前缀和，还原出每个学生最终的分数，顺便取最小值
    int mn = a[1];
    for (int i = 2; i <= n; i++) {
        a[i] += a[i - 1];
        if (a[i] < mn) mn = a[i];
    }
    printf("%d\n", mn);
    return 0;
}

易错点

• 用 cin 读 500 万个数 —— 本题最大的坑，必须快读或 scanf。
• 数组开小了：要用到 a[n+1]，而 n 最大 5×10⁶，所以开 5000005 这种带余量的。
• 忘记最后求前缀和：差分数组不是答案，必须累加还原。
• 求最小值时初值取 0：成绩都可能是正数，初值应该取 a[1]（或者取一个极大值），不要想当然写 0。
• 题面说「增加分数」，如果数据里出现负的 z，快读也要能读负数 —— 上面代码已经处理了。

题意：给一张 N 行 M 列的地图，每个格子有一个价值（可能是负数）。首都占一个 C×C 的正方形，要找一个位置放首都，让覆盖的格子价值总和最大，输出这个正方形左上角的坐标（行 列）。题目保证最优解唯一。

思路

先在 O(NM) 的时间里建好二维前缀和。然后枚举首都的左上角位置 (i, j)：

• 左上角是 (i, j)，边长是 C，那右下角就是 (i+C-1, j+C-1)；
• i 的范围是 1 ~ N-C+1，j 的范围是 1 ~ M-C+1（注意不是 1~N，否则右下角就越界了）；
• 每个位置用容斥公式 O(1) 算出正方形和，和当前最大值比较。

总复杂度 O(NM)，最大 10⁶ 次，飞快。

本题保证最优解唯一，所以不用纠结并列时输出哪一个。不过我还是用「严格大于才更新」的写法，保证一旦有并列会输出最靠上的那个，行为更确定。

3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1

1 2

边长 2 的正方形一共 6 种放法，和分别是：11、14、6、10、10、4。
最大的是 14，左上角在第 1 行第 2 列 → 输出 1 2。

完整代码

#include <iostream>
using namespace std;

const int MAXN = 1005;
long long sum[MAXN][MAXN];         // sum[i][j] = 左上角 (1,1) 到 (i,j) 的矩形和

int main() {
    ios::sync_with_stdio(false);   // 关掉同步，读 10^6 个数也不慢
    cin.tie(0);

    int N, M, C;
    cin >> N >> M >> C;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            long long v;
            cin >> v;
            // 容斥：上 + 左 - 左上角 + 自己
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + v;
        }
    }

    long long best = 0;
    int bx = 1, by = 1;
    bool first = true;             // 第一个位置无条件当擂主（价值可能是负数）
    for (int i = 1; i + C - 1 <= N; i++) {
        for (int j = 1; j + C - 1 <= M; j++) {
            int x2 = i + C - 1, y2 = j + C - 1;
            // 子矩形 (i,j)~(x2,y2) 的和，同样是容斥
            long long s = sum[x2][y2] - sum[i - 1][y2] - sum[x2][j - 1] + sum[i - 1][j - 1];
            if (first || s > best) { first = false; best = s; bx = i; by = j; }
        }
    }
    cout << bx << " " << by << endl;
    return 0;
}

易错点

• 用 int 存前缀和：最大能到 3.3×10¹⁰，会溢出成负数，答案直接错。必须 long long。
• 当成任意矩形做：题目只要「边长为 C 的正方形」，别去枚举长宽不同的矩形。
• 枚举范围写成 1~N：应该是 i + C - 1 <= N，否则右下角越界，读到数组外面去了。
• 输出的是左上角坐标，不是中心，也不是右下角。样例输出 1 2 就是「第 1 行第 2 列」。
• 全负数时初值给 0 会错：那样最大值就成了 0，而正确答案是个负数。初始化时把第一个位置无条件设成擂主最稳。

题意：在 n×n 的格子上铺 m 块矩形地毯，给出每块地毯的左上角和右下角。问每个格子被多少块地毯覆盖，输出整个 n×n 的答案矩阵。

思路

这就是二维差分的标准模板题，正好练「四个角点」。

1. 开一个 diff 数组当二维差分。每读一块地毯，只改 4 个点：左上 +1、右上 −1、左下 −1、右下 +1（注意这几行是地毯边界外一格：y2+1 和 x2+1）。
2. 所有地毯都记完之后，做一遍二维前缀和：d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]。做完之后 d[i][j] 就是「(i,j) 这一格被覆盖的次数」。
3. 按行输出。注意行末不要多打空格，换行用 \n。

复杂度：建表 O(m)，还原 O(n²)，总共 O(m + n²)，最大约 10⁶ 级别。

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

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

第 3 块地毯是 (1,2)~(1,4)，一条横着的，所以第 1 行右边三个格子的值从 0 变成了 1。

完整代码

#include <cstdio>

const int MAXN = 1005;
int d[MAXN][MAXN];                 // 二维差分数组

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

    for (int k = 0; k < m; k++) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        // 矩形 (x1,y1)~(x2,y2) 加 1，只用改 4 个点
        d[x1][y1]++;
        d[x1][y2 + 1]--;
        d[x2 + 1][y1]--;
        d[x2 + 1][y2 + 1]++;       // ★ 右下角补回来
    }

    // 二维前缀和还原
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d", d[i][j]);
            putchar(j == n ? '\n' : ' ');
        }
    }
    return 0;
}

// -------- 输出缓冲：攒满 4MB 再一次性写磁盘 --------
char obuf[1 << 22];
int olen = 0;

inline void pushChar(char c) {
    obuf[olen++] = c;
    if (olen == (1 << 22)) { fwrite(obuf, 1, olen, stdout); olen = 0; }
}
inline void writeInt(int x) {          // 手写整数转字符串，比 printf 快
    if (x == 0) { pushChar('0'); return; }
    char tmp[12]; int t = 0;
    while (x > 0) { tmp[t++] = (char)('0' + x % 10); x /= 10; }
    while (t > 0) pushChar(tmp[--t]);
}

// 输出时改成：writeInt(d[i][j]); pushChar(j == n ? '\n' : ' ');
// 程序最后记得把剩下的写出去：if (olen) fwrite(obuf, 1, olen, stdout);

易错点

• 四个角点的符号记错：左上 +、右上 −、左下 −、右下 +。记不住就直接套模板。
• 数组开成 n×n：要用到第 n+1 行第 n+1 列，必须多开。这里固定开 1005 就够了。
• 忘记做二维前缀和还原：不做的话输出的是差分数组，全是 0 和 ±1，肯定不对。
• 行末多打空格：用 j == n ? '\n' : ' ' 这种写法，行末就只有换行。
• 题目里的坐标是「(x1,y1) 左上、(x2,y2) 右下」，已经保证 x1≤x2、y1≤y2，不用自己交换。

题意：给一个 n×n 的矩阵，每个元素有整数权值（可为负）。要找一个大小不限的矩形（可以只取一格），使矩形里所有元素的权值和最大，输出这个最大和。

思路

矩形有四个自由度（上、下、左、右），全枚举是 O(n⁴)。我们想办法砍掉两个。

具体怎么 O(n) 求最大子段和？用前缀和版本：

设 S(j) = 第 1~j 列、第 top~bot 行的总和（这可以用二维前缀和 O(1) 得到：S(j) = sum[bot][j] - sum[top-1][j]）。 那么左右边界为 (l, r) 的矩形和就等于 S(r) - S(l-1)。

于是往右扫 j 的同时，记住「到目前为止见过的最小的 S」，用 S(j) - minPre 就能定出以 j 为右边界的最大矩形。这就是「最大子段和 = 前缀和的最大差」。

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

15

最优矩形是第 2~4 行、第 1~2 列：9+2+(−4)+1+(−1)+8 = 15。

完整代码

#include <cstdio>
#include <climits>

const int MAXN = 125;
int s[MAXN][MAXN];                 // s[i][j] = 左上角 (1,1) 到 (i,j) 这个矩形的和

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int v;
            scanf("%d", &v);
            // ★ 完整的二维前缀和：上 + 左 - 左上角 + 自己
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v;
        }
    }

    int best = INT_MIN;            // 全负数时答案就是最大的那个单个数
    for (int top = 1; top <= n; top++) {
        for (int bot = top; bot <= n; bot++) {
            // 固定上下边界后，第 top~bot 行、第 1~j 列的和就是
            //   S(j) = s[bot][j] - s[top-1][j]
            // 那么左右边界为 (l, r) 的矩形和 = S(r) - S(l-1)
            // 于是只要在 j 往右扫的过程中，记录「见过的最小 S」，就能 O(1) 定出最优左边界
            int minPre = 0;                    // 相当于 S(0) = 0
            for (int j = 1; j <= n; j++) {
                int S = s[bot][j] - s[top - 1][j];
                if (S - minPre > best) best = S - minPre;   // 以 j 为右边界的最优解
                if (S < minPre) minPre = S;                 // 更新"见过的最小前缀"
            }
        }
    }
    printf("%d\n", best);
    return 0;
}

易错点

• 用行前缀代替二维前缀：见上面的红色框，这是我亲自踩过的坑。
• 初值给 0：全负数矩阵的正确答案是负数，初值 0 会输出 0。用 INT_MIN，或者拿第一对上下边界的第一个结果当擂主。
• 写成标准 Kadane（cur 只跟 a[j] 有关）：这里扫的是前缀和数组 S，不是原数组。 对前缀和数组来说，cur = S[j] 相当于取了个空的左边界，会漏掉「从左边界 l 开始」的情况 —— 一定要用「S[j] − 见过的最小 S」这个形式。
• 枚举上下边界时 top ≤ bot：注意是 for(bot = top; bot <= n; bot++)，从 top 开始。
• 别担心内存：int s[125][125] 只有 62 KB。