洛谷 P3373 【模板】线段树 2

// P3373 第 ① 版：三种操作全都一个一个做
//
// ★ 题面把它的分数写好了：「30% 的数据 n ≤ 8，q ≤ 10」「70% 的数据 n ≤ 10³，q ≤ 10⁴」
//   ⇒ 70% 那一档最坏 10³ × 10⁴ = 10⁷ 次 ⇒ **稳拿 70 分**（本机毫秒级）。
//   顶格 n = q = 10⁵ 是 10¹⁰ ⇒ 0 分。
// ⚠ 它同时是参照物。

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

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

    long long n, q, mod;
    if (!(cin >> n >> q >> mod)) return 0;
    vector<long long> a(n + 1);
    for (long long i = 1; i <= n; i++) { cin >> a[i]; a[i] %= mod; }

    string out;
    for (long long i = 0; i < q; i++) {
        int op;
        long long x, y, k;
        cin >> op >> x >> y;
        if (op == 3) {
            long long s = 0;
            for (long long j = x; j <= y; j++) s = (s + a[j]) % mod;
            out += to_string(s);
            out += '\n';
        } else {
            cin >> k;
            k %= mod;
            for (long long j = x; j <= y; j++)
                a[j] = (op == 1) ? a[j] * k % mod : (a[j] + k) % mod;
        }
    }
    cout << out;
    return 0;
}

// P3373 正解 —— 线段树，两个懒标记（乘 + 加）
//
// ============ ★★★ 关键一步：把两个标记读成「一个仿射变换」============
//
//   一个节点欠儿子的账，现在是**两笔**：先乘 mul，再加 add。
//   把它写成一个函数：**f(x) = mul · x + add** —— 这就是一次**仿射变换**。
//
//   ★ 于是「两笔账怎么叠」这件事，就变成了「两个仿射变换怎么复合」，一行算完：
//
//       先做 f₁(x) = a₁x + b₁，再做 f₂(x) = a₂x + b₂
//       ⇒ f₂(f₁(x)) = a₂(a₁x + b₁) + b₂ = (a₂a₁)·x + (a₂b₁ + b₂)
//
//   ⇒ **新的 mul = a₂·a₁，新的 add = a₂·b₁ + b₂。**
//   ★★ 请注意 `a₂ · b₁` 这一项 —— 它就是所有人第一次都会漏掉的那句
//      「**乘的时候，原来欠着的加法标记也要跟着乘**」（见 p3373NoMul.cpp）。
//   ★★ 而「先乘后加」这个约定，也不是背下来的规矩，它就是上面那个式子的写法：
//      标记的含义一旦定成 f(x) = mul·x + add，下推的顺序就**只能**是先乘后加
//      （见 p3373Order.cpp）。
//
//   ⇒ 一句话：**两个标记的所有细节，都是「仿射变换复合」这一个式子的分量。**
//
// ============ ⚠ 要不要 long long：一句算术 ============
//
//   题面「除样例外 m = 571373」。节点的和 < m，标记 < m
//   ⇒ 中间值 sm[o] · mul 最大约 m² = 571373² ≈ **3.26 × 10¹¹** > 2³¹
//   ⇒ **int 必炸，long long 够用（余量 2800 万倍）。**
//   ⚠ 而**样例的 m 只有 38** ⇒ 中间值最大 1444 ⇒ **样例根本挡不住 int 版**（见 p3373Int.cpp）。
//
// 复杂度：每次操作 O(log n)。

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

const int MAXN = 100005;
long long sm[MAXN * 4], mul[MAXN * 4], add_[MAXN * 4];
long long a[MAXN];
long long n, q, mod;

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

/** 给节点 o（段长 len）施加一次仿射变换 x -> M·x + A */
inline void applyAff(int o, long long len, long long M, long long A) {
    sm[o] = (sm[o] * M + A % mod * len) % mod;
    mul[o] = mul[o] * M % mod;
    add_[o] = (add_[o] * M + A) % mod;          // ★★ 就是这个 add_[o] * M：旧的加法标记也要跟着乘
}

inline void pushdown(int o, int l, int r) {
    if (mul[o] == 1 && add_[o] == 0) return;
    int mid = (l + r) / 2;
    applyAff(o * 2, mid - l + 1, mul[o], add_[o]);
    applyAff(o * 2 + 1, r - mid, mul[o], add_[o]);
    mul[o] = 1; add_[o] = 0;                    // 销账：恒等变换
}

void build(int o, int l, int r) {
    mul[o] = 1; add_[o] = 0;
    if (l == r) { sm[o] = a[l] % mod; 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 M, long long A) {
    if (ql <= l && r <= qr) { applyAff(o, r - l + 1, M, A); return; }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, M, A);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, M, A);
    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 % mod;
}

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

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

    string out;
    for (long long i = 0; i < q; i++) {
        int op;
        long long x, y, k;
        cin >> op >> x >> y;
        if (op == 3) { out += to_string(query(1, 1, (int)n, (int)x, (int)y)); out += '\n'; }
        else {
            cin >> k;
            k %= mod;
            if (op == 1) update(1, 1, (int)n, (int)x, (int)y, k, 0);   // 乘 k：x -> k·x + 0
            else update(1, 1, (int)n, (int)x, (int)y, 1, k);           // 加 k：x -> 1·x + k
        }
    }
    cout << out;
    return 0;
}

// P3373 的生成器：./p3373Gen 种子 [档位]
//
// ★ 动笔之前先写清楚「每个版本靠什么现形」：
//   · p3373NoMul（乘的时候没乘旧的加法标记）→ 要**同一个节点上先欠加法、再来一次 M ≠ 1 的乘法**。
//     ⇒ 档 2（只有加法）和档 3（乘数恒为 1）都是**能证的 0**。
//   · p3373Order（sm 先加后乘）→ 要**同一段上 A 和 M 都不平凡** ⇒ 同样被档 2 / 档 3 挡死。
//   · p3373Int（树里用 int）→ 要中间值 sm·mul 越过 2³¹ ⇒ **模数说了算**：
//     ⚠ 档 0 用样例那个 m = 38 ⇒ 中间值最大 1444 ⇒ **精确的 0**；档 1 起换成题面的 571373。
//
// 档位：
//   0  ★ 顺手写的样子：n, q ∈ [6,12]，**模数照抄样例的 38**  ⇒ int 版精确的 0
//   1  ★ 照题面：模数 571373                                  ⇒ int 版现形
//   2  ★★ 只有「加」和「查」，没有乘法                        ⇒ 两个标记错法都是能证的 0
//   3  ★★ 有乘法，但乘数恒为 1                                ⇒ 同上（自检：0 不是因为代码没跑）
//   4  「70% 的数据」那一档：n = 10³、q = 10⁴（量暴力真实的秒数）
//   5  顶格 n = q = 10⁵，三种操作各三分之一
//   6  ⚠⚠ 区间**恒为整段 [1, n]** —— 我本来以为「两笔账全堆在根上 ⇒ 抓获率拉满」，
//      **实测是精确的 0，而且能证**：所有操作都全覆盖 ⇒ pushdown 一次都不执行
//      ⇒ 标记错成什么样都没人读得到（查询直接拿根上的 sm）。
//   7  ★★ 反过来：区间长度 ≤ 3 —— 逼着每次都往下走 ⇒ pushdown 密集
//
// ⚠ rng() 一律先落到具名变量再传参（[第 24 章 P1776](/sol/p1776/) 那一跤）。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937 rng(seed * 1000003u + 20260901u);

    int n, q;
    if (mode == 4) { n = 1000; q = 10000; }
    else if (mode == 5) { n = 100000; q = 100000; }
    else { n = 6 + (int)(rng() % 7u); q = 6 + (int)(rng() % 7u); }

    long long mod = (mode == 0) ? 38 : 571373;
    printf("%d %d %lld\n", n, q, mod);
    for (int i = 1; i <= n; i++) {
        int v = 1 + (int)(rng() % 10000u);
        printf("%d%c", v, i == n ? '\n' : ' ');
    }
    for (int t = 0; t < q; t++) {
        int x = 1 + (int)(rng() % (unsigned)n);
        int y = 1 + (int)(rng() % (unsigned)n);
        if (x > y) swap(x, y);
        if (mode == 6) { x = 1; y = n; }
        if (mode == 7) { int len = 1 + (int)(rng() % 3u); y = min(n, x + len - 1); }
        int op;
        if (mode == 2) op = (rng() % 2u == 0) ? 2 : 3;      // 只有加和查
        else op = 1 + (int)(rng() % 3u);
        if (op == 3) { printf("3 %d %d\n", x, y); continue; }
        int k;
        if (mode == 3 && op == 1) k = 1;                    // 乘数恒为 1
        else k = 1 + (int)(rng() % 10000u);
        printf("%d %d %d %d\n", op, x, y, k);
    }
    return 0;
}

// P3373 的度量程序：./p3373Count csv        （本页的数字都出自它）
//
//   down  : ★★★ 每一档里 **pushdown 真正执行了多少次** ——
//           这一个数就把「档 6（全整段）为什么是精确的 0」交代干净了：
//           所有操作都全覆盖 ⇒ 一次都不往下走 ⇒ 标记错成什么样都没人读得到。
//   line  : ★ int 版那条线是算术：中间值 sm·mul 最大约 m²。
//           样例的 m = 38 ⇒ 1444（int 绰绰有余）；题面的 m = 571373 ⇒ 3.26×10¹¹（int 的 152 倍）。
//   ms    : 70% 那一档（n=10³、q=10⁴）和顶格（n=q=10⁵）上暴力 / 线段树的毫秒。
//
// ⚠ 秒表一律用 steady_clock 在进程内量。
// ⚠ 这里**复刻**了 p3373Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。

#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, q; long long mod; vector<long long> a; vector<Op> ops; };

static Data gen(unsigned seed, int mode) {
    mt19937 rng(seed * 1000003u + 20260901u);
    Data d;
    int n, q;
    if (mode == 4) { n = 1000; q = 10000; }
    else if (mode == 5) { n = 100000; q = 100000; }
    else { n = 6 + (int)(rng() % 7u); q = 6 + (int)(rng() % 7u); }
    d.mod = (mode == 0) ? 38 : 571373;
    d.n = n; d.q = q; d.a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) d.a[i] = 1 + (int)(rng() % 10000u);
    for (int t = 0; t < q; t++) {
        int x = 1 + (int)(rng() % (unsigned)n);
        int y = 1 + (int)(rng() % (unsigned)n);
        if (x > y) swap(x, y);
        if (mode == 6) { x = 1; y = n; }
        if (mode == 7) { int len = 1 + (int)(rng() % 3u); y = min(n, x + len - 1); }
        int op;
        if (mode == 2) op = (rng() % 2u == 0) ? 2 : 3;
        else op = 1 + (int)(rng() % 3u);
        if (op == 3) { d.ops.push_back({3, x, y, 0}); continue; }
        int k;
        if (mode == 3 && op == 1) k = 1;
        else k = 1 + (int)(rng() % 10000u);
        d.ops.push_back({op, x, y, k});
    }
    return d;
}

static long long MOD, downCnt, nodeCnt;
static vector<long long> sm, mul_, add_;
static void applyAff(int o, long long len, long long M, long long A) {
    sm[o] = (sm[o] * M + A % MOD * len) % MOD;
    mul_[o] = mul_[o] * M % MOD;
    add_[o] = (add_[o] * M + A) % MOD;
}
static void down(int o, int l, int r) {
    if (mul_[o] == 1 && add_[o] == 0) return;
    downCnt++;
    int mid = (l + r) / 2;
    applyAff(o * 2, mid - l + 1, mul_[o], add_[o]);
    applyAff(o * 2 + 1, r - mid, mul_[o], add_[o]);
    mul_[o] = 1; add_[o] = 0;
}
static void build(int o, int l, int r, const vector<long long>& a) {
    mul_[o] = 1; add_[o] = 0;
    if (l == r) { sm[o] = a[l] % MOD; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid, a); build(o * 2 + 1, mid + 1, r, a);
    sm[o] = (sm[o * 2] + sm[o * 2 + 1]) % MOD;
}
static void upd(int o, int l, int r, int ql, int qr, long long M, long long A) {
    nodeCnt++;
    if (ql <= l && r <= qr) { applyAff(o, r - l + 1, M, A); return; }
    down(o, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) upd(o * 2, l, mid, ql, qr, M, A);
    if (qr > mid) upd(o * 2 + 1, mid + 1, r, ql, qr, M, A);
    sm[o] = (sm[o * 2] + sm[o * 2 + 1]) % MOD;
}
static long long qry(int o, int l, int r, int ql, int qr) {
    nodeCnt++;
    if (ql <= l && r <= qr) return sm[o];
    down(o, l, r);
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += qry(o * 2, l, mid, ql, qr);
    if (qr > mid) s += qry(o * 2 + 1, mid + 1, r, ql, qr);
    return s % MOD;
}
static vector<long long> segRun(const Data& d) {
    MOD = d.mod; sm.assign((size_t)d.n * 4 + 4, 0); mul_.assign((size_t)d.n * 4 + 4, 1);
    add_.assign((size_t)d.n * 4 + 4, 0);
    build(1, 1, d.n, d.a);
    vector<long long> out;
    for (const Op& o : d.ops) {
        if (o.type == 3) out.push_back(qry(1, 1, d.n, o.l, o.r));
        else if (o.type == 1) upd(1, 1, d.n, o.l, o.r, o.k % d.mod, 0);
        else upd(1, 1, d.n, o.l, o.r, 1, o.k % d.mod);
    }
    return out;
}
static vector<long long> bruteRun(const Data& d, long long& touched) {
    vector<long long> a(d.a), out;
    for (int i = 1; i <= d.n; i++) a[i] %= d.mod;
    touched = 0;
    for (const Op& o : d.ops) {
        if (o.type == 3) { long long s = 0; for (int j = o.l; j <= o.r; j++) { s = (s + a[j]) % d.mod; touched++; } out.push_back(s); }
        else for (int j = o.l; j <= o.r; j++) { a[j] = (o.type == 1) ? a[j] * (o.k % d.mod) % d.mod : (a[j] + o.k) % d.mod; touched++; }
    }
    return out;
}

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

    const int MODES[6] = {0, 1, 2, 3, 6, 7};
    long long downs[6] = {0}, nodes[6] = {0};
    for (int i = 0; i < 6; i++) {
        for (int s = 1; s <= 300; s++) {
            Data d = gen(s, MODES[i]);
            downCnt = 0; nodeCnt = 0;
            segRun(d);
            downs[i] += downCnt; nodes[i] += nodeCnt;
        }
    }

    Data d70 = gen(1, 4);
    long long touched = 0;
    auto t0 = steady_clock::now(); vector<long long> ob = bruteRun(d70, touched);
    double msB = duration<double, milli>(steady_clock::now() - t0).count();
    t0 = steady_clock::now(); vector<long long> os = segRun(d70);
    double msS = duration<double, milli>(steady_clock::now() - t0).count();
    bool same70 = (ob == os);

    Data dTop = gen(1, 5);
    t0 = steady_clock::now(); segRun(dTop);
    double msTop = duration<double, milli>(steady_clock::now() - t0).count();
    long long downTop = downCnt;

    long long m1 = 38LL * 38, m2 = 571373LL * 571373;

    if (csv) {
        for (int i = 0; i < 6; i++) printf("down%d,%lld\nnode%d,%lld\n", MODES[i], downs[i], MODES[i], nodes[i]);
        printf("sq38,%lld\nsq571373,%lld\n", m1, m2);
        printf("intTimes,%d\n", (int)(m2 / 2147483647LL));
        printf("ms70b,%.0f\nms70s,%.0f\ntouched70,%lld\n", msB, msS, touched);
        printf("msTop,%.0f\ndownTop,%lld\n", msTop, downTop);
        printf("same70,%d\n", same70 ? 1 : 0);
        return 0;
    }

    printf("① 每一档 300 轮里，pushdown 真正执行了多少次（这一个数解释了两个「精确的 0」）：\n\n");
    const char* NM[6] = {"0 顺手（模数 38）", "1 照题面（模数 571373）", "2 只有加和查",
                          "3 乘数恒为 1", "★ 6 区间恒为整段 [1,n]", "7 区间长度 ≤ 3"};
    for (int i = 0; i < 6; i++)
        printf("   %-26s pushdown %9lld 次 ｜ 递归到的节点 %10lld 个\n", NM[i], downs[i], nodes[i]);

    printf("\n② int 那条线（中间值 sm · mul 最大约 m²）：\n");
    printf("   样例的 m = 38      ⇒ %lld          （int 绰绰有余 ⇒ 样例挡不住 int 版）\n", m1);
    printf("   题面的 m = 571373  ⇒ %lld  （是 int 上限的 %lld 倍 ⇒ 必炸）\n", m2, m2 / 2147483647LL);

    printf("\n③ 秒表：\n");
    printf("   70%% 那一档 n=10³ q=10⁴ ： 暴力 %.0f ms（碰 %lld 格）｜线段树 %.0f ms，答案一致：%s\n",
           msB, touched, msS, same70 ? "是" : "★ 否");
    printf("   顶格 n=q=10⁵           ： 线段树 %.0f ms（pushdown %lld 次）\n", msTop, downTop);
    return 0;
}