我将 LeetCode 1109 题（航班预订统计）改写为了标准的 NOI/CSP 普及组/提高组风格题目。

本题是差分数组（Difference Array）最直接、最标准的应用场景。

[OI 基础训练] 空运物资统计 (差分数组应用)

一、 题目背景与知识点讲解

在之前的题目（如 LeetCode 370 区间加法）中，我们已经接触了差分数组的概念。本题是差分数组在实际业务场景下的直接映射。

场景描述： 你需要对一个长度为 $N$ 的数组进行 $M$ 次操作，每次操作都是将连续的一段区间 $[L, R]$ 内的所有数字加上一个特定的值 $V$。最后，你需要输出修改后的数组。

1. 暴力解法 (Brute Force) 对于每一条预订记录，使用循环将对应航班的座位数逐一累加。

• 复杂度：假设航班数 $N$，预订记录数 $M$。每次操作最坏需遍历 $N$ 个元素。总时间复杂度 $O(N \times M)$。
• 瓶颈：当 $N, M$ 均达到 $10^5$ 级别时，运算量为 $10^{10}$，远超计算机每秒 $10^8$ 次的运算能力，导致超时 (TLE)。

2. 优化解法：差分数组 (Difference Array) 利用差分数组，我们可以将“区间修改”的时间复杂度从 $O(N)$ 降低到 $O(1)$。

• 核心思想： 定义差分数组 $D[i] = A[i] - A[i-1]$。 如果我们想让原数组 $A$ 在区间 $[L, R]$ 上增加 $V$，在差分数组 $D$ 上的表现为：

  1. $D[L] += V$ （这就导致了 $A[L], A[L+1] \dots$ 及其后面的所有数相对于 $A[L-1]$ 都增加了 $V$）
  2. $D[R+1] -= V$ （为了抵消上面的增加，使得 $R$ 之后的数不受影响）

• 还原方法： 操作完成后，对差分数组 $D$ 求前缀和，即可得到最终的原数组 $A$。

• 复杂度分析：

  • 修改：$M$ 次操作，每次 $O(1)$。
  • 还原：遍历一次数组，复杂度 $O(N)$。
  • 总复杂度：$O(N + M)$。

二、 题目描述

IOI 航空公司拥有 $N$ 架飞机，编号从 $1$ 到 $N$。 航空公司接到了 $M$ 份预订订单。每一份订单信息包含三个整数：$First, Last, Seats$。 这表示从编号为 $First$ 的飞机到编号为 $Last$ 的飞机（包含 $First$ 和 $Last$），每架飞机都需要预留 $Seats$ 个座位。

请你计算并输出所有订单处理完毕后，每架飞机总共被预订了多少个座位。

注意： 初始时，所有飞机的预订座位数都为 0。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示飞机的数量和订单的数量。 接下来 $M$ 行，每行包含三个整数 $First, Last, Seats$，表示一条预订记录。

输出格式

输出一行，包含 $N$ 个整数，第 $i$ 个整数表示第 $i$ 架飞机的总预订座位数。整数之间用一个空格隔开。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le First \le Last \le N$
• $1 \le Seats \le 10,000$
• 提示：虽然单个订单座位数不大，但累加后可能会超过 int 范围，建议使用 long long。

样例输入

5 3
1 2 10
2 3 20
2 5 25

样例输出

10 55 45 25 25

样例解释

• 初始状态：[0, 0, 0, 0, 0]
• 订单 1 (1-2, +10)：[10, 10, 0, 0, 0]
• 订单 2 (2-3, +20)：[10, 30, 20, 0, 0]
• 订单 3 (2-5, +25)：[10, 55, 45, 25, 25]

三、 标准代码 (C++14 OI风格)

/**
 * 题目：空运物资统计 (Corporate Flight Bookings)
 * 知识点：差分数组 (Difference Array)
 * 时间复杂度：O(N + M)
 * 空间复杂度：O(N)
 */

#include <iostream>
#include <vector>

using namespace std;

// 使用 long long 防止累加过程中溢出
// 虽然本题 seats <= 10000，但 M 可达 2*10^5，总和可能达到 2*10^9，接近 int 极限
// 在 OI 中，涉及“求和”通常无脑上 long long 是比较稳妥的策略
typedef long long ll;

const int MAXN = 200005; 
// 差分数组，开大一点防止 diff[r+1] 越界
ll diff[MAXN]; 

int main() {
    // 1. IO 优化，加快大量数据的读写速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 2. 处理 M 条订单 (构建差分数组)
    for (int i = 0; i < m; ++i) {
        int l, r, v;
        cin >> l >> r >> v;

        // 核心差分操作：
        // 区间 [l, r] 增加 v
        // 相当于 diff[l] += v, diff[r+1] -= v
        diff[l] += v;
        diff[r + 1] -= v;
    }

    // 3. 还原原数组 (计算前缀和)并输出
    // current_seats 相当于前缀和 sum[i]
    ll current_seats = 0;
    for (int i = 1; i <= n; ++i) {
        current_seats += diff[i];
        
        // 按照题目要求格式输出
        cout << current_seats << (i == n ? "" : " ");
    }
    cout << "\n";

    return 0;
}

四、 教学备课重点 (教练参考)

1. 模型识别能力：

   • 教会学生如何从题目描述中提炼出数学模型。
   • 题目表述：“对第 $i$ 到第 $j$ 架飞机预订 $k$ 个座位”。
   • 数学模型：“对数组区间 $[i, j]$ 内的所有元素加上 $k$”。
   • 这种**“多次区间修改，一次最终查询”的模式，就是差分数组**的标准信号。

2. 边界问题 (Off-by-one Error)：

   • 题目中 $R$ 是飞机的编号（$1 \le R \le N$）。
   • 差分操作需要修改 diff[R+1]。
   • 易错点：如果数组只开到 $N$，当 $R=N$ 时，diff[N+1] 会导致数组越界。
   • 解决方案：数组大小至少开到 $N+2$。

3. 与线段树的取舍：

   • 很多学生学了线段树后，看到“区间修改”就想用线段树。
   • 引导：线段树支持“边修改、边查询”，复杂度是 $O(M \log N)$。虽然能过，但代码量大且常数大。
   • 本题是离线的（所有修改完成后才查询），差分数组 $O(N+M)$ 是最优解，且代码极短（核心仅 2 行）。

4. 数据类型：

   • 强调 long long 的重要性。即使题目现在的范围 int 可能刚好够用，但在 CSP/NOI 中，出题人经常会构造极限数据（例如 $N, M$ 很大，且 $Seats$ 也很大），导致 int 溢出变成负数。养成好习惯至关重要。