洛谷 P3372 【模板】线段树 1

// P3372 第 ① 版：最直白的暴力 —— 改一段就一个一个加，查一段就一个一个累
//
// ★ 它不是白写的：题面自己把它的分数写好了
//   「对于 15% 的数据：n ≤ 8，m ≤ 10」「对于 35% 的数据：n ≤ 10³，m ≤ 10⁴」
//   ⇒ 35% 那一档最坏 10³ × 10⁴ = 10⁷ 次，本机毫秒级 ⇒ **稳拿 35 分**。
//   而顶格 n = m = 10⁵ 是 10¹⁰ 次 ⇒ 一秒钟绝无可能。
//
// ⚠ 它同时是后面所有版本的**参照物**（对拍拿它当标准答案）。
//
// 复杂度：每次操作 O(区间长度)，总共 O(nm)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long k;
            cin >> k;
            for (int i = l; i <= r; i++) a[i] += k;       // 一个一个加
        } else {
            long long s = 0;
            for (int i = l; i <= r; i++) s += a[i];       // 一个一个累
            out += to_string(s);
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// P3372 正解 —— 线段树 + 懒标记（区间加 / 区间和）
//
// ★ 这就是[第 39 章](/ch/39-segment-tree/)正文那份 fast.cpp，**去掉了末行那三行 flush**：
//   本章那道题在真题基础上多要了一行「最终的整个数组」，而**真题不要**。
//   ⇒ 照着章节代码交上去会多打一行，`Wrong Answer`。
//
// ★★ lz[o] 的含义（背得一字不差，否则代码写不对）：
//   **「o 这个节点自己的 sm 已经算进去了，但 o 的两个儿子还不知道这件事。」**
//
// ★★★ 为什么这道题**不用担心溢出**（一句话，不用跑程序）：
//   题面写着「任意时刻数列的和不超过 2 × 10¹⁸」，
//   而线段树里的**每一个 sm[o] 都是某个子区间的和** ⇒ 每个都 ≤ 2 × 10¹⁸ < 9.22 × 10¹⁸。
//   ⇒ long long 够用，余量 4.6 倍。（和[第 38 章 P3374](/sol/p3374/) 那句是同一个形状的论证。）
//   ⚠ 但 lz 的累加和 x * len 也要一起看：len ≤ n，x 是单次加的值 ——
//     x * len 本身就是「这一段这次涨了多少」，同样被那句保证罩着。
//
// 复杂度：建树 O(n)，每次操作 O(log n)。

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

const int MAXN = 100005;
long long sm[MAXN * 4];                       // ⚠ 4n：n 不是 2 的幂时 2n 是不够的（见 p3372Size.cpp）
long long lz[MAXN * 4];
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

inline void applyAdd(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错
    lz[o] += x;                               // ★ 是 +=：欠了两笔账要叠起来
}

inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    applyAdd(o * 2, mid - l + 1, lz[o]);
    applyAdd(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { applyAdd(o, r - l + 1, x); return; }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);
    pushup(o);
}

long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// 「线段树的数组到底要开多大」—— 这是一道**算术题**，不用跑对拍
//
//   用法：./p3372Size          人话版
//         ./p3372Size csv      给 check:viz 用
//
// ★ 章节正文里那句「⚠ 数组要开 4n，2n 是不够的」是本章最常见的 RE 来源。
//   这份程序不制造越界（那是 UB，跑出来的数不可复现），它只**数**：
//   对每个 n，递归线段树真正用到的**最大节点下标**是多少。
//
// ★★★ 而这里有一件顺手写的测试**必然看不见**的事：
//   **n 是 2 的幂的时候，树是满的，最大下标正好 2n − 1 ⇒ 「只开 2n」完全够用。**
//   ⇒ 拿 n = 8 / 16 / 64 / 1024 试一遍，「开 2n」这个 bug 是**精确的 0**（实测 17 个全过）。
//   ⇒ 又一次「[顺手写的档位正好把 bug 喂对了](/sol/p1972/)」。
//
// ⚠⚠ 而这里还有一条**我的草稿被实测打回来**的：我本来写「官方样例 n = 5 就能戳穿它」——
//   **不对**。n = 5 的最大下标是 **9**，而 2n = 10 ⇒ **样例也挡不住**。
//   最小的反例是 **n = 6**（最大下标 13 > 12）。
//   ⇒ 「[样例是一测就死的过滤器](/sol/p1223/)」这条规律在这儿又拿到一个反例，
//     而这次连**下一个整数**就够了 —— 差一个 n。

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

static int mx;
static void walk(int o, int l, int r) {
    mx = max(mx, o);
    if (l == r) return;
    int mid = (l + r) / 2;
    walk(o * 2, l, mid);
    walk(o * 2 + 1, mid + 1, r);
}
static int maxIndex(int n) { mx = 0; walk(1, 1, n); return mx; }

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    const int LIM = 100000;                    // 题面顶格
    int firstOver2n = -1, firstOver3n = -1, worstN = 0;
    double worstRatio = 0;
    int pow2Bad = 0, pow2Cnt = 0;
    for (int n = 1; n <= LIM; n++) {
        int mi = maxIndex(n);
        if (firstOver2n < 0 && mi > 2 * n) firstOver2n = n;
        if (firstOver3n < 0 && mi > 3 * n) firstOver3n = n;
        double ratio = (double)mi / n;
        if (ratio > worstRatio) { worstRatio = ratio; worstN = n; }
        if ((n & (n - 1)) == 0) { pow2Cnt++; if (mi > 2 * n) pow2Bad++; }
    }
    int s5 = maxIndex(5), s8 = maxIndex(8);

    if (csv) {
        printf("firstOver2n,%d\n", firstOver2n);
        printf("firstOver3n,%d\n", firstOver3n);
        printf("worstN,%d\nworstRatio,%.3f\n", worstN, worstRatio);
        printf("over4n,%d\n", (worstRatio > 4.0) ? 1 : 0);
        printf("pow2Bad,%d\npow2Cnt,%d\n", pow2Bad, pow2Cnt);
        printf("sample5,%d\nsample5over,%d\n", s5, (s5 > 10) ? 1 : 0);
        printf("pow8,%d\npow8over,%d\n", s8, (s8 > 16) ? 1 : 0);
        return 0;
    }

    printf("n 从 1 数到 %d，看递归线段树真正用到的最大节点下标：\n\n", LIM);
    printf("  最先撑破 2n 的 n            = %d（它的最大下标 %d > %d）\n",
           firstOver2n, maxIndex(firstOver2n), 2 * firstOver2n);
    printf("  最先撑破 3n 的 n            = %d\n", firstOver3n);
    printf("  最大下标 / n 的最大值       = %.3f（在 n = %d 取到）⇒ 开 4n 够，开 3n 不够\n",
           worstRatio, worstN);
    printf("  ★ n 是 2 的幂的那 %d 个     : 撑破 2n 的有 %d 个（树是满的，下标恰好 2n−1）\n",
           pow2Cnt, pow2Bad);
    printf("\n  官方样例 n = 5：最大下标 %d，而 2n = 10 ⇒ %s\n",
           s5, s5 > 10 ? "★ 只开 2n 当场越界" : "开 2n 够用");
    printf("  顺手测的 n = 8：最大下标 %d，而 2n = 16 ⇒ %s\n",
           s8, s8 > 16 ? "越界" : "★ 开 2n 够用 —— 所以拿 2 的幂去测，这个 bug 一次都不现形");
    return 0;
}

// P3372 第 ③ 版：**两个树状数组**也能做「区间加 + 区间和」
//
// ★ 为什么要写它：[第 39 章第 13 步](/ch/39-segment-tree/)把「线段树 vs 树状数组」摆在一起，
//   结论是「树状数组代码短、常数小，线段树能干的事多」。**这一版把那笔账反过来算了一遍** ——
//   连这一章的模板题，树状数组也做得下来，而且更短更快。
//
// ============ 推导（[第 6 章](/ch/06-prefix-diff/)那套差分，往前多推一步）============
//
//   记差分 d[i] = a[i] − a[i−1]。区间加 [l,r] += k 就是 d[l] += k、d[r+1] −= k（两个单点改）。
//   而 a 的前缀和：
//
//     Σ_{i=1..x} a[i] = Σ_{i=1..x} Σ_{j=1..i} d[j]
//                     = Σ_{j=1..x} (x − j + 1) · d[j]
//                     = (x+1) · Σ_{j=1..x} d[j]  −  Σ_{j=1..x} j · d[j]
//
//   ⇒ 维护**两个**树状数组就够了：B1 存 d[j]，B2 存 j·d[j]。
//   ⇒ 区间加是 4 次单点改，区间和是 4 次前缀查，全都 O(log n)。
//
// ============ ⚠⚠ 但它有一处线段树没有的隐患：中间值 j · d[j] ============
//
//   题面只保证「**数列的和**不超过 2 × 10¹⁸」。线段树里每个 sm[o] 都是某个子区间的和
//   ⇒ 全被那句话罩住了。**而 j · d[j] 不是任何一个区间的和** ——
//   合法输入里它能到 10⁵ × 2×10¹⁸ = **2 × 10²³**，是 long long 上限的两万多倍。
//   ★ 那它到底会不会算错？见 p3372Count.cpp 的 `wrap` 那一行 —— 结论和
//   [第 38 章 P3374](/sol/p3374/) 那条一模一样：**「它溢出了」和「它算错了」是两件事。**
//   ⚠ 但有符号溢出是 UB，考场上别赌 —— 这一版存在的意义是「短、快」，不是「安全」。
//
// 复杂度：每次操作 O(log n)，常数比线段树小得多（没有递归、没有下推）。

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

const int MAXN = 100005;
long long c1[MAXN], c2[MAXN];                  // c1: d[j]；c2: j·d[j]
int n, m;

inline void add(long long* c, int i, long long v) {
    for (; i <= n; i += i & -i) c[i] += v;
}
inline long long ask(long long* c, int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i) s += c[i];
    return s;
}

/** 区间 [l,r] 每个数 += k —— 差分之后是两个单点改，两个数组各改两处 */
inline void rangeAdd(int l, int r, long long k) {
    add(c1, l, k);            add(c2, l, (long long)l * k);
    if (r + 1 <= n) { add(c1, r + 1, -k); add(c2, r + 1, -(long long)(r + 1) * k); }
}

/** a 的前缀和 Σ_{i=1..x} a[i] = (x+1)·Σd − Σ j·d[j] */
inline long long prefix(int x) {
    return (long long)(x + 1) * ask(c1, x) - ask(c2, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        rangeAdd(i, i, x);                     // 建树就是「把每个 a[i] 当成一次长度为 1 的区间加」
    }

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long k;
            cin >> k;
            rangeAdd(l, r, k);
        } else {
            out += to_string(prefix(r) - prefix(l - 1));
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// P3372 的度量程序：./p3372Count csv        （本页的数字都出自它）
//
//   cap    : ★ 自检 —— 每一档里「任意时刻的总和」的最大值，对照题面那句 2×10¹⁸。
//            **生成器必须亲手守住它**，否则测的是一组题目不会给的输入。
//   line   : ★★ int 版的触发线是**算出来的**：档 1（值域 10⁶、n=m≈12）最大和只有 1.56×10⁸，
//            离 2³¹ 差 13.8 倍 ⇒ 那一档必然是**精确的 0**（[第 6 章 P3406](/sol/p3406/) 那条的复现）。
//   trig   : ★★★ 档 2 上两层数：① 有查询的答案越过 2³¹ 的轮数 ② int 版真被抓的轮数。
//   bitMax : ★★★ 档 4（巨值）上，双树状数组的中间量 j·d[j] 的**真值**（用 __int128 算），
//            对照 long long 上限 —— 这是「BIT 版 60 轮全对」那个 0 的**自检**：
//            先证明它真的溢出了，那句「溢出 ≠ 答错」才有意义。
//   ms     : 35% 那一档（n=10³、m=10⁴）和顶格（n=m=10⁵）上三种做法的毫秒。
//   ops    : 换一把机器无关的尺子 —— 三种做法各「碰了多少个格子 / 走了多少步」。
//
// ⚠ 秒表一律用 steady_clock 在进程内量（[第 35 章 P2866](/sol/p2866/) 那一跤：
//   拿 shell 里的时间戳相减，带着约 100 毫秒的固定开销）。
// ⚠ 这里**复刻**了 p3372Gen.cpp 的档位逻辑（同一个 mt19937_64、同一个种子公式）。

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

struct Op { int type, l, r; long long k; };
struct Data { int n, m; vector<long long> a; vector<Op> ops; };

static const long long CAP = 2000000000000000000LL;

/** ⚠ 和 p3372Gen.cpp 一字对应 */
static Data gen(unsigned seed, int mode) {
    mt19937_64 rng(seed * 1000003ull + 20260901ull);
    Data d;
    int n, m;
    if (mode == 3) { int e = 3 + (int)(rng() % 4u); n = 1 << e; m = 8 + (int)(rng() % 8u); }
    else if (mode == 4) { n = 100000; m = 20; }
    else if (mode == 5) { n = 1000; m = 10000; }
    else if (mode == 6 || mode == 7) { n = 100000; m = 100000; }
    else { n = 6 + (int)(rng() % 7u); m = 6 + (int)(rng() % 7u); }

    long long hi;
    if (mode == 0) hi = 100;
    else if (mode == 1) hi = 1000000;
    else if (mode == 4) hi = 1;
    else hi = CAP / ((long long)n * (m + 1));
    if (hi < 1) hi = 1;

    d.n = n; d.m = m; d.a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long v;
        if (mode == 4) v = (i == n) ? (CAP / 2) : 1;
        else v = 1 + (long long)(rng() % (unsigned long long)hi);
        d.a[i] = v;
    }
    for (int q = 0; q < m; q++) {
        int l = 1 + (int)(rng() % (unsigned)n);
        int r = 1 + (int)(rng() % (unsigned)n);
        if (l > r) swap(l, r);
        if (mode == 7) { l = 1; r = n; }
        int op;
        if (mode == 7) op = (q % 8 == 7) ? 2 : 1;
        else if (mode == 4) op = (q % 3 == 0) ? 1 : 2;
        else op = 1 + (int)(rng() % 2u);
        long long k = 0;
        if (op == 1) {
            if (mode == 4) k = 1 + (long long)(rng() % 1000ull);
            else k = 1 + (long long)(rng() % (unsigned long long)hi);
        }
        d.ops.push_back({op, l, r, k});
    }
    return d;
}

/** 直接模拟：返回「任意时刻总和的最大值」和「被问到的答案的最大值」 */
static void simulate(const Data& d, __int128& maxTotal, __int128& maxAns) {
    vector<__int128> a(d.n + 1, 0);
    __int128 total = 0;
    for (int i = 1; i <= d.n; i++) { a[i] = d.a[i]; total += a[i]; }
    maxTotal = total; maxAns = 0;
    for (const Op& o : d.ops) {
        if (o.type == 1) {
            for (int i = o.l; i <= o.r; i++) a[i] += o.k;
            total += (__int128)o.k * (o.r - o.l + 1);
            if (total > maxTotal) maxTotal = total;
        } else {
            __int128 s = 0;
            for (int i = o.l; i <= o.r; i++) s += a[i];
            if (s > maxAns) maxAns = s;
        }
    }
}

/** 档 4 上，双树状数组的中间量 j·d[j] 能到多大（真值，__int128） */
static __int128 bitIntermediate(const Data& d) {
    vector<__int128> diff(d.n + 2, 0);
    for (int i = 1; i <= d.n; i++) diff[i] += d.a[i], diff[i + 1] -= d.a[i];
    for (const Op& o : d.ops)
        if (o.type == 1) { diff[o.l] += o.k; if (o.r + 1 <= d.n) diff[o.r + 1] -= o.k; }
    __int128 best = 0;
    for (int j = 1; j <= d.n; j++) {
        __int128 v = (__int128)j * diff[j];
        if (v < 0) v = -v;
        if (v > best) best = v;
    }
    return best;
}

/* ---------------- 三种做法，都带一把「走了多少步」的尺子 ---------------- */
static long long steps;

static vector<long long> bruteRun(const Data& d) {
    vector<long long> a(d.n + 1), out;
    for (int i = 1; i <= d.n; i++) a[i] = d.a[i];
    for (const Op& o : d.ops) {
        if (o.type == 1) { for (int i = o.l; i <= o.r; i++) { a[i] += o.k; steps++; } }
        else { long long s = 0; for (int i = o.l; i <= o.r; i++) { s += a[i]; steps++; } out.push_back(s); }
    }
    return out;
}

static int SN;
static vector<long long> sm, lz;
static void sBuild(int o, int l, int r, const vector<long long>& a) {
    steps++; lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    sBuild(o * 2, l, mid, a); sBuild(o * 2 + 1, mid + 1, r, a);
    sm[o] = sm[o * 2] + sm[o * 2 + 1];
}
static void sApply(int o, int len, long long x) { sm[o] += x * len; lz[o] += x; steps++; }
static void sDown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    sApply(o * 2, mid - l + 1, lz[o]); sApply(o * 2 + 1, r - mid, lz[o]); lz[o] = 0;
}
static void sUpd(int o, int l, int r, int ql, int qr, long long x) {
    steps++;
    if (ql <= l && r <= qr) { sApply(o, r - l + 1, x); return; }
    sDown(o, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) sUpd(o * 2, l, mid, ql, qr, x);
    if (qr > mid) sUpd(o * 2 + 1, mid + 1, r, ql, qr, x);
    sm[o] = sm[o * 2] + sm[o * 2 + 1];
}
static long long sQry(int o, int l, int r, int ql, int qr) {
    steps++;
    if (ql <= l && r <= qr) return sm[o];
    sDown(o, l, r);
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += sQry(o * 2, l, mid, ql, qr);
    if (qr > mid) s += sQry(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}
static vector<long long> segRun(const Data& d) {
    SN = d.n; sm.assign((size_t)d.n * 4 + 4, 0); lz.assign((size_t)d.n * 4 + 4, 0);
    sBuild(1, 1, d.n, d.a);
    vector<long long> out;
    for (const Op& o : d.ops) {
        if (o.type == 1) sUpd(1, 1, d.n, o.l, o.r, o.k);
        else out.push_back(sQry(1, 1, d.n, o.l, o.r));
    }
    return out;
}

static vector<long long> c1v, c2v;
static void bAdd(vector<long long>& c, int i, long long v) { for (; i <= SN; i += i & -i) { c[i] += v; steps++; } }
static long long bAsk(vector<long long>& c, int i) { long long s = 0; for (; i > 0; i -= i & -i) { s += c[i]; steps++; } return s; }
static void bRange(int l, int r, long long k) {
    bAdd(c1v, l, k); bAdd(c2v, l, (long long)l * k);
    if (r + 1 <= SN) { bAdd(c1v, r + 1, -k); bAdd(c2v, r + 1, -(long long)(r + 1) * k); }
}
static long long bPre(int x) { return (long long)(x + 1) * bAsk(c1v, x) - bAsk(c2v, x); }
static vector<long long> bitRun(const Data& d) {
    SN = d.n; c1v.assign(d.n + 2, 0); c2v.assign(d.n + 2, 0);
    for (int i = 1; i <= d.n; i++) bRange(i, i, d.a[i]);
    vector<long long> out;
    for (const Op& o : d.ops) {
        if (o.type == 1) bRange(o.l, o.r, o.k);
        else out.push_back(bPre(o.r) - bPre(o.l - 1));
    }
    return out;
}

template <class F> static double timeIt(F f, long long& st) { steps = 0; auto t0 = steady_clock::now();
    f(); st = steps; return duration<double, milli>(steady_clock::now() - t0).count(); }

static string i128(__int128 v) {
    if (v == 0) return "0";
    string s; bool neg = v < 0; if (neg) v = -v;
    while (v) { s += char('0' + (int)(v % 10)); v /= 10; }
    if (neg) s += '-';
    reverse(s.begin(), s.end());
    return s;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 自检：每一档都守住了题面那句「任意时刻的和 ≤ 2×10¹⁸」吗 */
    int capBad = 0;
    __int128 capWorst = 0;
    for (int mode : {0, 1, 2, 3, 5, 6, 7}) {
        int rounds = (mode >= 5) ? 3 : 60;
        for (int s = 1; s <= rounds; s++) {
            Data d = gen(s, mode);
            __int128 mt, ma; simulate(d, mt, ma);
            if (mt > capWorst) capWorst = mt;
            if (mt > CAP) capBad++;
        }
    }

    /* ② int 版的触发线：档 1 够不着，档 2 够得到 */
    const long long INT_MAX_LL = 2147483647LL;
    int trig1 = 0, trig2 = 0;
    __int128 max1 = 0;
    for (int s = 1; s <= 300; s++) {
        Data d1 = gen(s, 1), d2 = gen(s, 2);
        __int128 mt, ma;
        simulate(d1, mt, ma); if (ma > max1) max1 = ma; if (ma > INT_MAX_LL) trig1++;
        simulate(d2, mt, ma); if (ma > INT_MAX_LL) trig2++;
    }

    /* ③ 档 4：双树状数组的中间量到底多大 */
    __int128 bitWorst = 0;
    for (int s = 1; s <= 20; s++) {
        Data d = gen(s, 4);
        __int128 v = bitIntermediate(d);
        if (v > bitWorst) bitWorst = v;
    }
    double bitTimes = (double)bitWorst / 9.223372036854775807e18;

    /* ④ 秒表 + 步数 */
    long long stB = 0, stS = 0, stT = 0;
    Data d35 = gen(1, 5);                       // 35% 那一档
    double msB35 = timeIt([&] { bruteRun(d35); }, stB);
    double msS35 = timeIt([&] { segRun(d35); }, stS);
    double msT35 = timeIt([&] { bitRun(d35); }, stT);
    long long stB35 = stB, stS35 = stS, stT35 = stT;

    Data dTop = gen(1, 6);                      // 顶格
    double msSTop = timeIt([&] { segRun(dTop); }, stS);
    double msTTop = timeIt([&] { bitRun(dTop); }, stT);
    long long stSTop = stS, stTTop = stT;

    Data dAll = gen(1, 7);                      // 顶格且全整段（懒标记最占便宜）
    double msSAll = timeIt([&] { segRun(dAll); }, stS);
    long long stSAll = stS;

    bool same35 = (bruteRun(d35) == segRun(d35)) && (segRun(d35) == bitRun(d35));

    if (csv) {
        printf("capBad,%d\ncapWorstOver2e18,%d\n", capBad, (capWorst > CAP) ? 1 : 0);
        printf("capWorstPct,%d\n", (int)((long double)capWorst * 100 / CAP));
        printf("trig1,%d\ntrig2,%d\n", trig1, trig2);
        printf("max1,%s\n", i128(max1).c_str());
        printf("max1Gap,%d\n", (int)((long double)INT_MAX_LL / (long double)max1));
        printf("bitWorst,%s\nbitTimesLL,%d\n", i128(bitWorst).c_str(), (int)bitTimes);
        printf("ms35b,%.0f\nms35s,%.0f\nms35t,%.0f\n", msB35, msS35, msT35);
        printf("st35b,%lld\nst35s,%lld\nst35t,%lld\n", stB35, stS35, stT35);
        printf("msTops,%.0f\nmsTopt,%.0f\n", msSTop, msTTop);
        printf("stTops,%lld\nstTopt,%lld\n", stSTop, stTTop);
        printf("msAll,%.0f\nstAll,%lld\n", msSAll, stSAll);
        printf("same35,%d\n", same35 ? 1 : 0);
        return 0;
    }

    printf("① 自检：七个档共 %d 组，越过题面那句 2×10¹⁸ 的有 %d 组（最大用到额度的 %d%%）\n\n",
           7, capBad, (int)((long double)capWorst * 100 / CAP));
    printf("② int 版的触发线（被问到的答案要越过 2³¹−1 = %lld）：\n", INT_MAX_LL);
    printf("   档 1（值域 10⁶）：300 轮里触发 %d 次 —— 最大答案才 %s，差 %d 倍，**够不着**\n",
           trig1, i128(max1).c_str(), (int)((long double)INT_MAX_LL / (long double)max1));
    printf("   档 2（顶到题面保证）：300 轮里触发 %d 次\n\n", trig2);
    printf("③ 档 4：双树状数组的中间量 j·d[j] 最大 = %s\n", i128(bitWorst).c_str());
    printf("   而 long long 上限是 9223372036854775807 ⇒ **超出 %d 倍**（它真的溢出了）\n\n",
           (int)bitTimes);
    printf("④ 秒表 / 步数：\n");
    printf("   35%% 那一档 n=10³ m=10⁴ ： 暴力 %.0f ms（%lld 步）｜线段树 %.0f ms（%lld 步）｜树状数组 %.0f ms（%lld 步）\n",
           msB35, stB35, msS35, stS35, msT35, stT35);
    printf("   顶格 n=m=10⁵          ： 线段树 %.0f ms（%lld 步）｜树状数组 %.0f ms（%lld 步）\n",
           msSTop, stSTop, msTTop, stTTop);
    printf("   顶格且全是整段修改      ： 线段树 %.0f ms（%lld 步）\n", msSAll, stSAll);
    printf("   三种做法答案一致：%s\n", same35 ? "是" : "★ 不一致！");
    return 0;
}