P4761 最要强的飞行员（入门）

解题思路

故事里有 n 个据点，每个据点都有牢固值；m 轮攻击会各自攻打一段连续的据点，飞行员想挑"总牢固值最大"的那一轮去出战。所以这道题就是：给 m 个区间，分别求出每个区间的和，再找出其中的最大值。

如果每轮攻击都用循环从头把区间里的数字加一遍，假设 n 和 m 都很大，会非常慢。我们用前缀和来加速：先算出 pre[i] 表示前 i 个据点的牢固值之和。那么第 L 到第 R 个据点的总牢固值就是 pre[R] - pre[L-1]，一次减法就出结果，复杂度从 O(区间长度) 变成了 O(1)。

接下来很简单：读入 m 轮的范围，每轮算出一个区间和 s，用一个变量 ans 记录目前最大的那个。如果 s 比 ans 大，就把 ans 更新成 s。所有轮次处理完之后，ans 就是答案。

用样例验证：n=7，牢固值 2 10 5 3 6 4 9。第 1 轮打 3~5，和是 5+3+6=14；第 2 轮打 6~7，和是 4+9=13。两轮里最大的是 14，正好是输出。

边界情况要想到：ans 一开始可以设成 -1，因为牢固值都是正整数，第一轮算出来的和一定比 -1 大，这样 ans 一定会被正确更新。另外 n 和 m 最大都是 500000，数组开到 500005，用 long long 存前缀和，防止数字相加溢出。

参考代码

// 求 m 轮攻击中总牢固值的最大值：先用前缀和求出每轮范围的和，再取最大
#include <iostream>
int main() {
    int n, m;
    std::cin >> n >> m;
    long long pre[500005] = {0}; // pre[i] 表示前 i 个据点的牢固值之和
    for (int i = 1; i <= n; ++i) {
        long long x;
        std::cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    long long ans = -1; // 记录最大的总牢固值
    for (int i = 0; i < m; ++i) {
        int L, R;
        std::cin >> L >> R;
        long long s = pre[R] - pre[L - 1]; // 区间 L~R 的和
        if (s > ans) ans = s;
    }
    std::cout << ans << '\n';
    return 0;
}

复杂度分析

建前缀和数组要 O(n) 时间，处理 m 个区间每个 O(1)，所以总时间复杂度是 O(n+m)。空间上多开一个 pre 数组，是 O(n)。n 和 m 都最大 500000，加起来大约 100 万次操作，运行非常快，用最普通的枚举法（每个区间从头加）最坏会到 O(n*m)=2500 亿次，根本比不了，这就是前缀和的威力。