洛谷 P8218 【深进1.例1】求区间和

// P8218 的第 ① 版：每次询问从 l 老老实实加到 r
//
// ★ 它**不是没用的** —— 题面明写着「对于 50% 的数据：n, m ≤ 1000」，
//   这一版在那一半数据上稳稳当当，**考场上就是实打实的 50 分**。
//   ⇒ 第 45 章那条考场策略：**先把暴力写对，再想办法做快**；
//     不会正解的时候，暴力是分数，不是废纸。
//
// ⚠ 它在满数据上是 O(nm)：n = m = 1e5、每次都问整段 ⇒ 100 亿次加法。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        long long sum = 0;
        for (int i = l; i <= r; i++) sum += a[i];     // ← 同一段被反复加
        cout << sum << '\n';
    }
    return 0;
}

// P8218【深进1.例1】求区间和 —— 能 AC 的那一版：一维前缀和
//
// s[i] = a[1] + a[2] + … + a[i]，于是 [l, r] 的和就是 s[r] - s[l-1]。
//
// ⚠ 两处下标：
//   ① **前缀和数组从 1 开始存**（s[0] = 0 当哨兵）。这样 l = 1 时 s[l-1] = s[0] = 0，
//      不用写任何特判。要是把 a 存在 0..n-1 上，`s[l-1]` 在 l = 1 时就是 s[-1] —— 越界。
//   ② 询问给的 l、r 都是 1 基的，别自己再减一次。
//
// ★ 上界算一遍（第 45 章那一课）：n ≤ 1e5、a_i ≤ 1e4 ⇒ 总和最大 1e9，
//   而 int 的上限是 2 147 483 647 —— **恰好装得下，余量只有 2.1 倍**。
//   ⇒ 这题 int 能用，但值得知道自己站在哪儿：a_i 的上界再大一位，int 就废了。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> s(n + 1, 0);           // s[0] = 0 —— 这个哨兵省掉了 l = 1 的特判
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }
    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';     // ⚠ 用 '\n' 不用 endl（endl 每次都刷缓冲区）
    }
    return 0;
}

// 数据生成器（P8218 对拍用）：`./p8218Gen <seed> [level]`
//
//   level 0（默认）随机 n <= 12、m <= 8，a_i <= 20，区间随机
//   level 1        专挑边界：一半的询问是 l = 1（会用到 s[0] 那个哨兵）、
//                  l = r（单个数）、以及 l = 1 且 r = n（整段）
//
// ★ 为什么要有 level 1：这道题唯一能写错的地方就是 `s[l-1]` 那个下标，
//   而它**只在 l = 1 时才露头**。顺手随机的话，l = 1 的概率是 1/n ——
//   n = 12 时三百轮当然撞得上，可换成 n = 1e5 的规模就永远撞不上了。
//   ⇒ 「小数据随机」和「小数据 + 专挑边界」不是一回事，正文第 ④ 步有那张表。

#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), m = ri(1, 8);
    printf("%d\n", n);
    for (int i = 1; i <= n; i++) printf("%d%c", ri(1, 20), i == n ? '\n' : ' ');
    printf("%d\n", m);
    for (int i = 0; i < m; i++) {
        int l, r;
        if (level == 1 && ri(0, 2) == 0) { l = 1; r = n; }            // 整段
        else if (level == 1 && ri(0, 1) == 0) { l = 1; r = ri(1, n); }// 贴着左端
        else if (level == 1) { l = r = ri(1, n); }                    // 单个数
        else { l = ri(1, n); r = ri(l, n); }
        printf("%d %d\n", l, r);
    }
    return 0;
}

// 两笔账：① 两种写法各做了多少次加法；② int 到底够不够用
//
// 用法：./p8218Count <n> <m>        人话版
//       ./p8218Count <n> <m> csv    只打 `键,值`，给 check:viz 用
//
// ① 尺子：**最坏形状**（每个询问都是 1..n）下
//      暴力 = n × m 次加法；前缀和 = n 次（预处理）+ m 次（每问一次减法）。
// ② 上界：题面给的是 n ≤ 1e5、a_i ≤ 1e4 ⇒ 总和最大 1e9。
//    ★ 这一笔一定要在写代码之前算，而不是等 WA 了再算 —— 第 45 章那一课。

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

int main(int argc, char** argv) {
    long long n = (argc > 1) ? atoll(argv[1]) : 100000;
    long long m = (argc > 2) ? atoll(argv[2]) : 100000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    long long brute = n * m;                 // 最坏形状：每次都加满一整段
    long long fast = n + m;
    long long maxSum = 100000LL * 10000;     // 题面上界：n × max(a_i)
    long long intMax = 2147483647LL;
    if (csv) {
        printf("n,%lld\nm,%lld\nbrute,%lld\nfast,%lld\nratio,%lld\n"
               "maxSum,%lld\nintMax,%lld\nfitsInt,%d\nheadroom,%lld\n",
               n, m, brute, fast, brute / fast, maxSum, intMax,
               maxSum <= intMax ? 1 : 0, intMax / maxSum);
    } else {
        printf("n = %lld, m = %lld（最坏形状：每个询问都是 1..n）\n", n, m);
        printf("① 暴力     %lld 次加法\n", brute);
        printf("② 前缀和   %lld 次（预处理 n 次 + 每问一次减法）\n", fast);
        printf("⇒ 差 %lld 倍\n\n", brute / fast);
        printf("题面上界：n <= 100000、a_i <= 10000 ⇒ 区间和最大 %lld\n", maxSum);
        printf("int 的上限                                    %lld\n", intMax);
        printf("⇒ %s，余量 %lld 倍\n", maxSum <= intMax ? "装得下" : "装不下", intMax / maxSum);
    }
    return 0;
}