P2367 语文成绩 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P2367，日期见页头。两边不一致时信原站。

题目背景：语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 n、p，代表学生数与增加分数的次数。

第二行有 n 个数，a₁ ~ aₙ，代表各个学生的初始成绩。

接下来 p 行，每行有三个数 x、y、z，代表给第 x 个到第 y 个学生每人增加 z 分。

输出格式：输出仅一行，代表更改分数后，全班的最低分。

数据范围

对于 40% 的数据，有 n ≤ 10³；
对于 60% 的数据，有 n ≤ 10⁴；
对于 80% 的数据，有 n ≤ 10⁵；
对于 100% 的数据，有 n ≤ 5 × 10⁶，p ≤ n，学生初始成绩 ≤ 100，z ≤ 100。

输入输出样例

输入

输出

3 个学生初始都是 1 分；1 2 1 给第 1~~2 个各加 1 分，2 3 1 给第 2~~3 个各加 1 分。最后是 2 3 2，最低分 2。上面那段输出是仓库里的 p2367.cpp 真跑出来的。

1先盯住数据范围里那个数：n ≤ 5 × 10⁶

这道题的算法是第 6 章后半场的模板（差分，三行），真正决定分数的是另一件事：

n ≤ 5 000 000，p ≤ n
⇒ 最坏要读 5×10⁶ + 3×5×10⁶ = 两千万个整数
⇒ 输入文件本身就有 100 MB 左右
而时限是 1 秒

★ 「读入」在这道题上不是常数，是主项。 第 ④ 步会把四种读法量给你看 —— 结论会有点吓人：连 scanf 都不够。

2第 ① 版：题目怎么说就怎么做（40 分）

p2367Brute.cpp第 ① 版：一个一个加

样例当然对。它挂的是规模。

// P2367 的第 ① 版：题目怎么说就怎么做 —— 每次操作，把 [x, y] 里每个人的成绩加上 z
//
// ★ 它在「对于 40% 的数据，n ≤ 10³」那一档上稳过（最多 10⁶ 次加法），
//   ⇒ 考场上的 40 分。⚠ 满数据 n = p = 5×10⁶、每次都覆盖全班 ⇒ 2.5×10¹³ 次加法。
//
// 慢在哪一眼可见：**同一个人被反复加了无数遍**，而最后只问一次最低分。
// 第 6 章后半场的「关键的一步」就是从这句话里长出来的：**只记变化量**。

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

static int a[5000005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < p; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        for (int j = x; j <= y; j++) a[j] += z;      // ← 一个一个加
    }
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++) ans = min(ans, a[i]);
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

本机实测（B 机：原生 Ubuntu 7.0.0-30 / i5-10210U 8 线程 / 18 GB，2026-08-26，独占；最坏形状：每次操作都覆盖全班）：

`n = p`	① 一个一个加	② 差分
1 000（40% 那一档）	★ 0.00 秒	0.00 秒
10 000	0.02 秒	0.00 秒
50 000	0.44 秒	0.00 秒
200 000	7.75 秒	0.00 秒
5 000 000（满数据）	约 4400 秒（按 `n²` 外推）	★ 0.59 秒

★ 它在「40% 的数据 n ≤ 10³」那一档上稳过 —— 考场上是实打实的 40 分，而写它只要五行。⚠ 但注意：这道题的部分分是按 n 分档的， n ≤ 10⁵ 那一档（80%）它也过不去（10¹⁰ 次加法）。

3第 ② 版：差分 —— 只记变化量

d[x] += z;
d[y + 1] -= z;         // ⚠ 数组要开到 n+1：y = n 时这一行会写 d[n+1]

最后对 d 求一遍前缀和，就还原出「第 i 个人一共加了多少」。

p2367.cpp第 ② 版：差分 + 快读（能 AC）

// P2367 语文成绩 —— 能 AC 的那一版：差分 ＋ 快读
//
// 算法就是第 6 章后半场那三行：
//   区间 [x, y] 每人加 z  ⇒  d[x] += z; d[y+1] -= z;
//   最后对 d 求一遍前缀和，就还原出每个人加了多少。
// O(n + p) 代替 O(np)。
//
// ★★ 但这道题真正卡人的**不是算法，是读入**：n ≤ 5×10⁶、p ≤ n ⇒
//   最坏要读 5×10⁶ + 3×5×10⁶ = **两千万个整数**，而时限只有 1 秒。
//   本机实测（正文第 ④ 步）：同一个差分算法，用默认的 cin 读要 3.5 秒，用快读 0.35 秒。
//   ⇒ 第 45 章那一节（四种读法差多少）在这道题上是**分数线**，不是趣味知识。
//
// 快读的原理：一次 fread 把一大块字节拿进来，自己拼数字，
// 不经过任何格式解析（scanf 那套 `%d` 的解析器）。

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

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;

static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc(), s = 1, x = 0;
    while (c != EOF && (c < '0' || c > '9') && c != '-') c = gc();
    if (c == '-') { s = -1; c = gc(); }
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x * s;
}

static int a[5000005];
static int d[5000006];                       // ⚠ 要开到 n+1：y = n 时会写 d[n+1]

int main() {
    int n = readInt(), p = readInt();
    for (int i = 1; i <= n; i++) a[i] = readInt();
    for (int i = 0; i < p; i++) {
        int x = readInt(), y = readInt(), z = readInt();
        d[x] += z;
        d[y + 1] -= z;                       // ← 差分的全部内容就这两行
    }
    int cur = 0, ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
        cur += d[i];                         // 前缀和还原「第 i 个人一共加了多少」
        ans = min(ans, a[i] + cur);
    }
    printf("%d\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠ 两个下标，和一个不用担心的账

d[y+1]：y 可以等于 n，所以数组必须开到 n + 1。这是差分唯一能写错的地方，对拍档位 1 专门盯它。
ans 不用开 long long：最低分最大是 100 + 100 × p ≤ 100 + 5×10⁸，离 int 的 2.1×10⁹ 还差四倍。★ 这一笔仍然要算 —— 算完确认不用，和没算过是两回事。

4★★★ 这道题的第二关：四种读法，只有一种过得去

同一个差分算法，只把读入换掉：

p2367Read.cpp四种读法跑同一个差分

参数是 n（默认 100 万，满数据是 500 万；页面上跑 100 万就够看出形状了）。它自己造数据，不用喂输入。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

// P2367 的第二关：同一个差分算法，四种读法差多少
//
// 用法：./p2367Read [n] [csv]      默认 n = 1000000（满数据是 5000000）
//   ★ 它自己造一份 P2367 形状的输入写进临时文件，再 freopen 回 stdin 读四遍 ——
//     不需要喂输入。四遍的**答案必须一模一样**（csv 里的 same 就是钉这件事的）。
//
// 四种读法（第 45 章第 11 步解释过它们的区别，这里量的是**这道题上的**代价）：
//   ① cin（默认，同步开着）    ② cin + sync_with_stdio(false)
//   ③ scanf                    ④ 手写快读（fread 整块读进来自己拼数字）
//
// ⚠ 顺序不能换：关掉同步之后 cin 会自己预读一大块，之后再 freopen 换文件，
//   cin 缓冲里剩的就是上一份文件的残渣 ⇒ 「同步开着」那一趟必须排在最前面
//   （这条坑是第 45 章 read.cpp 里踩过的，照抄它的顺序）。

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

static char path[64];
static int a[5000005];
static int d[5000006];

static void makeData(int n) {
    snprintf(path, sizeof(path), "/tmp/p2367-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件 %s\n", path); exit(1); }
    mt19937 rng(20260826u);
    fprintf(f, "%d %d\n", n, n);
    for (int i = 0; i < n; i++) fprintf(f, "%d%c", (int)(rng() % 101), i + 1 == n ? '\n' : ' ');
    for (int i = 0; i < n; i++) {
        int x = 1 + (int)(rng() % (unsigned)n);
        int y = x + (int)(rng() % (unsigned)(n - x + 1));
        fprintf(f, "%d %d %d\n", x, y, (int)(rng() % 101));
    }
    fclose(f);
}
static void reopen() {
    if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); }
}

/* 差分那三行 —— 四趟共用，所以四趟之间的差别只可能来自读入 */
static int finish(int n) {
    int cur = 0, ans = INT_MAX;
    for (int i = 1; i <= n; i++) { cur += d[i]; ans = min(ans, a[i] + cur); }
    return ans;
}
static void reset(int n) { memset(d, 0, sizeof(int) * (size_t)(n + 2)); }

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    makeData(n);
    double ms[4];
    int ans[4];

    /* ① cin（默认，同步开着）—— 必须排第一趟 */
    { reopen(); reset(n);
      auto t0 = steady_clock::now();
      int m, p; cin >> m >> p;
      for (int i = 1; i <= m; i++) cin >> a[i];
      for (int i = 0; i < p; i++) { int x, y, z; cin >> x >> y >> z; d[x] += z; d[y + 1] -= z; }
      ans[0] = finish(m);
      ms[0] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ② cin + sync_with_stdio(false) */
    { reopen(); reset(n);
      auto t0 = steady_clock::now();
      ios::sync_with_stdio(false); cin.tie(nullptr);
      int m, p; cin >> m >> p;
      for (int i = 1; i <= m; i++) cin >> a[i];
      for (int i = 0; i < p; i++) { int x, y, z; cin >> x >> y >> z; d[x] += z; d[y + 1] -= z; }
      ans[1] = finish(m);
      ms[1] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ③ scanf */
    { reopen(); reset(n);
      auto t0 = steady_clock::now();
      int m, p; if (scanf("%d %d", &m, &p) != 2) { m = p = 0; }
      for (int i = 1; i <= m; i++) { if (scanf("%d", &a[i]) != 1) break; }
      for (int i = 0; i < p; i++) {
          int x, y, z;
          if (scanf("%d %d %d", &x, &y, &z) != 3) break;
          d[x] += z; d[y + 1] -= z;
      }
      ans[2] = finish(m);
      ms[2] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ④ 手写快读 */
    { reopen(); reset(n); ipos = ilen = 0;
      auto t0 = steady_clock::now();
      int m = readIntFast(), p = readIntFast();
      for (int i = 1; i <= m; i++) a[i] = readIntFast();
      for (int i = 0; i < p; i++) {
          int x = readIntFast(), y = readIntFast(), z = readIntFast();
          d[x] += z; d[y + 1] -= z;
      }
      ans[3] = finish(m);
      ms[3] = duration<double, milli>(steady_clock::now() - t0).count(); }

    remove(path);
    bool same = (ans[0] == ans[1] && ans[1] == ans[2] && ans[2] == ans[3]);
    if (csv) {
        const char* key[4] = { "cin", "nosync", "scanf", "fast" };
        for (int k = 0; k < 4; k++) printf("%s,%.1f\n", key[k], ms[k]);
        printf("same,%d\nanswer,%d\n", same ? 1 : 0, ans[0]);
        return 0;
    }
    const char* name[4] = { "cin（默认，同步开着）", "cin + sync_with_stdio(false)",
                            "scanf", "手写快读（fread）" };
    /* ⚠ 中文是双宽的，%-30s 按字节数补空格会补歪 —— 照第 45 章 read.cpp 那套按显示宽度补 */
    auto disp = [](const string& t) {
        int w = 0;
        for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; }
        return w;
    };
    auto padR = [&](const string& t, int w) { return t + string(max(0, w - disp(t)), ' '); };
    double best = *min_element(ms, ms + 4);
    printf("n = p = %d（和满数据比是 %.0f%%），四种读法跑同一个差分：\n\n", n, 100.0 * n / 5000000);
    for (int k = 0; k < 4; k++)
        printf("  %s %8.1f 毫秒   慢 %4.1f 倍\n", padR(name[k], 30).c_str(), ms[k], ms[k] / best);
    printf("\n四趟的答案%s（都是 %d）\n", same ? "完全一致" : "居然不一致！", ans[0]);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

本机实测（同机同日独占，n = p = 5 × 10⁶ 满数据）：

读法	毫秒	比最快的慢	1 秒时限
`cin`（默认，同步开着）	8 139.7	11.9 倍	✗
`cin` + `sync_with_stdio(false)`	2 676.6	3.9 倍	✗
`scanf`	3 029.1	4.4 倍	✗
手写快读（`fread`）	★ 682.3	1.0 倍	★ ✓

★★★ 连 scanf 都不够 —— 这是「读入优化」真正成为分数线的那种题

第 45 章第 11 步量过这四种读法的差别，那里的结论是「cin 默认最慢、快读最快」。这道题把那张表变成了及格线：

大多数人的第一反应 cin（不关同步）：8.1 秒，八倍超时。
加一句 ios::sync_with_stdio(false)：2.7 秒 —— 快了三倍，还是超。
换成 scanf：3.0 秒 —— 和上一条一个量级，还是超。
手写 fread 快读：0.68 秒，过。

⇒ 判断要不要写快读，看的不是「题目难不难」，而是要读多少个数。这道题两千万个 —— 而 scanf 一个数大约 150 纳秒，光解析就 3 秒。 ★ 经验值：读入量到 10⁶ 就该关同步，到 10⁷ 就该上快读。

p2367Cin.cpp对照：算法一样，读入用默认 cin

5★ 对拍：600 轮，两档

p2367Gen.cpp生成器：两个档位

参数是「种子档位」。档位 1 专挑 x = 1 / y = n / x = y / z = 0。

// 数据生成器（P2367 对拍用）：`./p2367Gen <seed> [level]`
//
//   level 0（默认）随机 n <= 12、p <= 8，成绩 0..100，z 0..100，区间随机
//   level 1        专挑边界：x = 1、y = n、x = y，以及 z = 0
//
// ★ 为什么要有 level 1：差分唯一能写错的地方是那两个下标 ——
//   `d[y+1] -= z` 在 y = n 时会写到 d[n+1]（数组必须开到 n+1，不然就是越界），
//   而 `d[x] += z` 在 x = 1 时是数组的第一个位置。
//   顺手随机的话，「y 正好等于 n」的概率是 1/n。

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

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);
    int n = ri(1, 12), p = ri(1, 8);
    printf("%d %d\n", n, p);
    for (int i = 1; i <= n; i++) printf("%d%c", ri(0, 100), i == n ? '\n' : ' ');
    for (int i = 0; i < p; i++) {
        int x, y;
        if (level == 1) {
            int kind = ri(0, 3);
            if (kind == 0) { x = 1; y = n; }                 // 整段
            else if (kind == 1) { x = ri(1, n); y = n; }     // 贴着右端 —— 会写 d[n+1]
            else if (kind == 2) { x = 1; y = ri(1, n); }     // 贴着左端
            else { x = y = ri(1, n); }                       // 只有一个人
        } else { x = ri(1, n); y = ri(x, n); }
        printf("%d %d %d\n", x, y, level == 1 && ri(0, 3) == 0 ? 0 : ri(0, 100));
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

check:viz 每档 300 轮，暴力当标准答案 —— 两档都是 300 / 300 逐字节相同。

★ 档位 1 盯的是 d[y+1]：y 正好等于 n 的时候，那一行会写到数组的最后一格之外。顺手随机的话它的概率是 1/n，专门造就是每四次一次。

6三个版本并排

版本	算法	读入	满数据	分数
① `p2367Brute`	一个一个加 `O(np)`	`cin` 关同步	约 4400 秒	★ 40 分
② `p2367Cin`	差分 `O(n+p)`	`cin` 默认	6.85 秒	✗ 超时
③ `p2367`	差分 `O(n+p)`	快读	★ 0.59 秒	★ 100 分

★ 中间那一行是这一页的全部意思：算法对了，仍然可能因为读入而挂掉。

⚠ 这张表的秒数是两份真程序端到端跑满数据（p2367Cin / p2367，输入从文件喂进去）；上一步那张表是 p2367Read 在一个进程里连跑四趟量的（每趟 freopen 重读同一份数据）。两组数不完全相等（6.85 ↔ 8.1、0.59 ↔ 0.68）很正常 —— 它们量的边界不一样，但结论是同一个：只有快读那一档在 1 秒以内。

这一页记住三句话

★ 先读数据范围再动手。 n ≤ 5×10⁶ 这个数同时决定了三件事：要用差分、要开 2000 万个数的读入预算、以及数组开多大。
★★★ 「读入优化」不是玄学，是这道题的及格线。 cin 8.1 秒 / 关同步 2.7 秒 / scanf 3.0 秒 / 快读 0.68 秒，时限 1 秒。 ⇒ 读入量 10⁶ 关同步，10⁷ 上快读。
⚠ d[y+1] 要开到 n+1。 差分唯一能写错的地方，而它只在 y = n 时露头 —— 对拍要专门造这一档。

洛谷 P2367 语文成绩

0题目原文（本地存了一份）

输入

输出

1先盯住数据范围里那个数：n ≤ 5 × 10⁶

2第 ① 版：题目怎么说就怎么做（40 分）

3第 ② 版：差分 —— 只记变化量

4★★★ 这道题的第二关：四种读法，只有一种过得去

5★ 对拍：600 轮，两档

6三个版本并排