题目分析与思路提示

1. 为什么暴力法会死机？

如果用直接模拟的方法：

• 有一个数组 a[N]。
• 对于每次指令 $L, R, K$，我们用 for(j = L; j <= R; j++) a[j] += K;。
• 复杂度分析：
  • 单次操作最坏需要遍历 $N$ 个元素。
  • $M$ 次操作，总复杂度 $O(N \times M)$。
  • 数据范围 $N, M$ 高达 $10^6$。$10^6 \times 10^6 = 10^{12}$。
  • 计算机 1 秒只能算 $10^8$ 次。这需要算几个小时！绝对超时。

我们需要一种 $O(1)$ 的方式来完成“区间加法”。

2. 核心算法：差分数组 (Difference Array)

差分是前缀和的逆运算。 定义差分数组 $D$，其中 $D[i] = A[i] - A[i-1]$（规定 $A[0]=0$）。

神奇的性质： 如果我们想让原数组 $A$ 在区间 $[L, R]$ 上的每个数都加上 $K$：

• 对于差分数组 $D$，只需要做两步操作：
  1. D[L] += K
  2. D[R+1] -= K
• 原理：
  • D[L] += K 意味着从 $L$ 开始，每个数通过前缀和还原时都会多加一个 $K$。
  • D[R+1] -= K 意味着从 $R+1$ 开始，把之前多加的那个 $K$ 抵消掉（因为 $R+1$ 及之后不需要加）。

算法流程：

1. 定义差分数组 diff，大小为 $N+2$（防止 $R+1$ 越界），初始化为 0。
2. 读取 $M$ 条指令，每条指令执行：
   • diff[L] += K
   • diff[R+1] -= K
   • 单次操作复杂度 $O(1)$。
3. 还原数组：
   • 对 diff 数组求前缀和，即可还原出最终的兵力数组 $A$。
   • $A[i] = A[i-1] + diff[i]$（或直接用变量累加）。
   • 总还原复杂度 $O(N)$。
4. 在还原的过程中，打擂台维护最小值 min_val。

总时间复杂度：$O(M + N)$。对于 $10^6$ 的数据，轻轻松松。

参考代码 (C++14)

/**
 * 题目：长城防线 (Great Wall Defense)
 * 难度：GESP 6级
 * 算法：差分数组 (Difference Array)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 1000005; 
// 差分数组，开大一点防止 R+1 越界
// 兵力可能累加得很大，虽然K<=1000, M<=10^6 => 10^9，int勉强够，但推荐 long long
long long diff[MAXN]; 

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // 1. 处理 M 次修改 (O(M))
    for (int i = 0; i < M; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        
        // 差分核心操作
        diff[l] += k;       // 区间起点 +k
        diff[r + 1] -= k;   // 区间终点的下一位 -k
    }

    // 2. 还原原数组并找最小值 (O(N))
    long long current_val = 0;
    long long min_val = -1; // 初始化标记

    for (int i = 1; i <= N; ++i) {
        // 前缀和还原：当前位置的值 = 上一位置的值 + 当前位置的差分
        // 也就是 current_val += diff[i]
        current_val += diff[i];

        // 寻找最小值
        if (i == 1) {
            min_val = current_val;
        } else {
            if (current_val < min_val) {
                min_val = current_val;
            }
        }
    }

    cout << min_val << endl;

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
long long solve(int N, int M, const vector<tuple<int, int, int>>& ops) {
    vector<long long> diff(N + 2, 0);
    for (const auto& op : ops) {
        int l = get<0>(op);
        int r = get<1>(op);
        int k = get<2>(op);
        diff[l] += k;
        diff[r + 1] -= k;
    }

    long long current = 0;
    long long min_v = -1;
    
    // 还原并找最小
    for (int i = 1; i <= N; ++i) {
        current += diff[i];
        if (i == 1) min_v = current;
        else min_v = min(min_v, current);
    }
    return min_v;
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<tuple<int, int, int>> ops;

        // 构造测试点
        if (i == 1) { 
            // 样例
            N = 5; M = 3;
            ops = {{1,3,2}, {2,4,3}, {3,5,1}};
        }
        else if (i <= 3) {
            // 小规模
            N = 100; M = 100;
            for(int k=0; k<M; k++) {
                int l = randRange(1, N);
                int r = randRange(l, N);
                ops.emplace_back(l, r, randRange(1, 10));
            }
        }
        else if (i == 4) {
            // 全覆盖测试 (最小值很大)
            N = 1000; M = 1000;
            for(int k=0; k<M; k++) {
                ops.emplace_back(1, N, 10);
            }
        }
        else if (i == 5) {
            // 稀疏覆盖 (最小值可能为0)
            N = 10000; M = 10;
            for(int k=0; k<M; k++) {
                int l = randRange(1, N-100);
                ops.emplace_back(l, l+50, 100);
            }
        }
        else if (i == 6) {
            // 单点修改 (L=R)
            N = 10000; M = 10000;
            for(int k=0; k<M; k++) {
                int l = randRange(1, N);
                ops.emplace_back(l, l, randRange(1, 100));
            }
        }
        else {
            // 大规模压力测试
            // N, M 达到 10^6
            // 为了生成器运行不过慢，这里设为 5*10^5，实际题目支持 10^6
            N = 500000; M = 500000;
            for(int k=0; k<M; k++) {
                int l = randRange(1, N);
                int r = randRange(l, N);
                ops.emplace_back(l, r, randRange(1, 100));
            }
        }

        // 写入输入
        fin << N << " " << M << endl;
        for(const auto& op : ops) {
            fin << get<0>(op) << " " << get<1>(op) << " " << get<2>(op) << "\n";
        }

        // 写入输出
        fout << solve(N, M, ops) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}