题目分析与思路提示

1. 为什么暴力法不行？

如果直接模拟，对于每次查询 $u \to v$，我们用一个 for 循环从 $u$ 加到 $v$。

• 最坏情况下，每次查询都要遍历整个数组（例如从 1 到 $N$）。单次查询复杂度 $O(N)$。
• 一共有 $M$ 次查询，总复杂度是 $O(N \times M)$。
• 代入数据：$10^5 \times 10^5 = 10^{10}$ 次运算。
• C++ 一般限制 1 秒约 $10^8$ 次运算。暴力法会超时 (Time Limit Exceeded)。

我们需要一种 $O(1)$ 的方法来回答区间求和问题。

2. 核心算法：前缀和 (Prefix Sum)

这是 GESP 6级必须掌握的技巧。 我们定义一个数组 sum，其中 sum[i] 表示从城市 1 到城市 $i$ 的总成本。

• sum[1] = 0 （1到1距离为0）
• sum[2] = $W_1$
• sum[3] = $W_1 + W_2$
• ...
• sum[i] = sum[i-1] + $W_{i-1}$ （即加上第 $i-1$ 段河道的成本）

利用前缀和求区间和： 如果我们要计算从城市 $L$ 到城市 $R$ ($L < R$) 的距离：

• 从 1 走到 $R$ 的成本是 sum[R]。
• 从 1 走到 $L$ 的成本是 sum[L]。
• 那么 $L$ 到 $R$ 的成本就是 sum[R] - sum[L]。

通俗理解：这就好比刻度尺。你想知道 10cm 到 25cm 有多长，不需要重新数格子，只需要用 $25 - 10 = 15$。

3. 算法流程

1. 预处理：读入 $W$ 数组时，顺便计算 sum 数组。
   • sum[1] = 0
   • sum[i+1] = sum[i] + w
   • 复杂度 $O(N)$。
2. 查询：对于每个询问 $u, v$：
   • 如果 $u > v$，交换它们（因为路费是对称的）。
   • 输出 sum[v] - sum[u]。
   • 复杂度 $O(1)$。
3. 总复杂度：$O(N + M)$。对于 $10^5$ 的数据，可以秒出。

4. 细节与坑点

• 数据类型：虽然单个 $W_i$ 很小，但 $N$ 个累加起来可能很大。$10^5 \times 10^4 = 10^9$，接近 int 极限。如果是 $10^9$ 的数据范围则必须用 long long。本题虽然勉强在 int 范围内，但为了稳妥，建议 sum 数组使用 long long。
• 下标对应：城市编号从 1 到 $N$，河段有 $N-1$ 个。前缀和数组 sum 的大小要开到 $N+1$。
• 输入顺序：查询可能是 $4 \to 2$，计算时记得 swap 成 $2 \to 4$ 或者取 abs(sum[4] - sum[2])。

参考代码 (C++14)

/**
 * 题目：漕运成本 (Canal Transport Cost)
 * 难度：GESP 6级
 * 算法：前缀和 (Prefix Sum)
 */

#include <iostream>
#include <vector>
#include <cmath> // 用于 abs 或 swap
#include <algorithm>

using namespace std;

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

const int MAXN = 100005;
// sum[i] 表示从城市 1 到城市 i 的总成本
// 使用 long long 防止溢出
long long sum[MAXN]; 

int main() {
    fast_io();

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

    // 1. 预处理前缀和
    // 城市 1 的前缀和是 0
    sum[1] = 0;

    for (int i = 1; i < N; ++i) {
        int w;
        cin >> w;
        // 关键递推式：到第 i+1 个城市的成本 = 到第 i 个城市的成本 + 第 i 段路的权重
        sum[i + 1] = sum[i] + w;
    }

    // 2. 处理查询
    for (int k = 0; k < M; ++k) {
        int u, v;
        cin >> u >> v;

        // 确保 u <= v，或者直接取差值的绝对值
        if (u > v) {
            swap(u, v);
        }

        // 利用前缀和公式 O(1) 求解
        // 区间 [u, v] 的和 = sum[v] - sum[u]
        // 注意：这里 sum[u] 代表的是 1到u 的距离，相减后正好剩下 u到v 的距离
        long long cost = sum[v] - sum[u];
        
        cout << cost << "\n"; // 使用 \n 比 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)
// ------------------------------------------
void solve(int N, const vector<int>& W, const vector<pair<int, int>>& queries, ofstream& fout) {
    // 构造前缀和
    vector<long long> sum(N + 1, 0);
    for (int i = 0; i < N - 1; ++i) {
        sum[i + 2] = sum[i + 1] + W[i];
    }

    for (const auto& q : queries) {
        int u = q.first;
        int v = q.second;
        if (u > v) swap(u, v);
        fout << sum[v] - sum[u] << "\n";
    }
}

// 辅助函数
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<int> W;
        vector<pair<int, int>> queries;

        // 构造测试点
        if (i == 1) { 
            // 样例
            N = 5; M = 3;
            W = {2, 5, 1, 4};
            queries = {{1, 3}, {4, 2}, {1, 5}};
        }
        else if (i <= 3) {
            // 小规模随机
            N = 100; M = 50;
            for(int k=0; k<N-1; k++) W.push_back(randRange(1, 100));
            for(int k=0; k<M; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }
        else if (i == 4) {
            // 链状全1测试 (距离=坐标差)
            N = 1000; M = 1000;
            for(int k=0; k<N-1; k++) W.push_back(1);
            for(int k=0; k<M; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }
        else if (i == 5) {
            // 逆序查询测试 (u > v)
            N = 1000; M = 1000;
            for(int k=0; k<N-1; k++) W.push_back(randRange(1, 1000));
            for(int k=0; k<M; k++) {
                int u = randRange(2, N);
                int v = randRange(1, u-1);
                queries.push_back({u, v});
            }
        }
        else if (i == 6) {
            // 长距离查询 (1 到 N)
            N = 5000; M = 10;
            for(int k=0; k<N-1; k++) W.push_back(randRange(100, 200));
            for(int k=0; k<M; k++) queries.push_back({1, N});
        }
        else {
            // 大规模随机 (N, M = 10^5)
            N = 100000; M = 100000;
            for(int k=0; k<N-1; k++) W.push_back(randRange(1, 10000));
            for(int k=0; k<M; k++) queries.push_back({randRange(1, N), randRange(1, N)});
        }

        // 写入输入
        fin << N << " " << M << endl;
        for(int k=0; k<N-1; k++) {
            fin << W[k] << (k == N-2 ? "" : " ");
        }
        fin << endl;
        for(const auto& q : queries) {
            fin << q.first << " " << q.second << "\n";
        }

        // 写入输出
        solve(N, W, queries, fout);

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