很好小朋友们，我们被要求写一个可持久化线段树，支持区间修改、区间复制和输出区间和。

懒标记是必须的，但可持久化线段树一般不太支持 pushdown，尤其在本题中。

在进入子节点之前，我们需要克隆当前节点，因为当前节点可能被其他版本共享。

然后才能将其懒标记下推到新克隆出的子节点，最后将当前节点的懒标记重置。

这样会导致不必要的新节点开销。

于是我们不考虑 pushdown，而是在递归函数中同时传进祖先变化，即懒标记。

线段树维护五个参数，分别是左右子节点、区间总和 $b、c$ 懒标记。

（1）处理操作 0

我们构建一个 change 函数，对版本 p 的区间 $[l, r]$ 施加变换 $x -> b*x + c$，返回新版本的根节点。

可持久化的精髓是“改了才新建”，编写时请注意祖先变化的传递。

（2）处理操作 1

一个个复制绝对是不明智的，我们可以先构建一个 crossover 函数。

合并两个版本 $x$ 和 $y$，返回一个新版本，其前 $at$ 个元素来自 $x$，后 $len - at$ 个元素来自 y。

这样题目的 $[l, r]$ 可以变成先处理 $[1, r]$ 的复制，接着把原来的 $[1, l - 1]$ 复制回去。

（3）处理操作 2

正常的 query 函数即可。

另注意：本题的边界和 base 十分复杂，我用的是统一 base-1。

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const LL P = 998244353;          // 模数
const int N = 1e5 + 10;          // 数组最大长度
 
#define lc(p) tr[p].lc           // 左孩子下标
#define rc(p) tr[p].rc           // 右孩子下标
#define MID ((L + R) >> 1)       // 当前区间中点
 
/*
  线段树节点结构：
    lc, rc    : 左右孩子指针（下标）
    sum       : 当前节点代表的区间和（已应用该节点的懒标记）
    lazy_b, lazy_c : 懒标记，表示对子区间施加的仿射变换 x -> lazy_b * x + lazy_c
*/
struct node {
    int lc, rc;
    LL sum;
    LL lazy_b, lazy_c;
};
 
vector<node> tr;                 // 动态存储所有节点，0 号节点为空节点
LL a[N];                         // 原始数组（1‑based）
 
// 新建一个节点，懒标记初始为恒等变换 (1, 0)
int newd() {
    tr.push_back({0, 0, 0, 1, 0});
    return (int)tr.size() - 1;
}
 
// 克隆节点 p，复制其所有信息
int clone_node(int p) {
    tr.push_back(tr[p]);
    return (int)tr.size() - 1;
}
 
/*
  将仿射变换 x -> b*x + c 应用到节点 p 所代表的整个区间（长度为 len）
  同时更新该节点的懒标记，使其与原有懒标记复合。
  注意：应用顺序为 新变换 作用于 旧变换，即最终变换为 b*(old(x)) + c。
*/
void modify(int p, LL b, LL c, LL len) {
    if (p == 0) return;
    tr[p].sum = (b * tr[p].sum + c * len) % P;
    tr[p].lazy_b = b * tr[p].lazy_b % P;
    tr[p].lazy_c = (b * tr[p].lazy_c % P + c) % P;
}
 
// 复合变换：返回 g(f())，即先 f 后 g
pair<LL, LL> compose(LL g_b, LL g_c, LL f_b, LL f_c) {
    return { (g_b * f_b) % P, (g_b * f_c + g_c) % P };
}
 
// 用左右子树的 sum 更新当前节点的 sum
void pushup(int p) {
    tr[p].sum = (tr[lc(p)].sum + tr[rc(p)].sum) % P;
}
 
// 建树，p 为引用返回根节点下标
void build(int &p, int L, int R) {
    p = newd();
    if (L == R) {
        tr[p].sum = a[L] % P;
        return;
    }
    build(lc(p), L, MID);
    build(rc(p), MID + 1, R);
    pushup(p);
}
 
/*
  对版本 p 的区间 [l, r] 施加变换 x -> b*x + c，返回新版本的根节点。
  参数 prop_b, prop_c 表示从根到当前节点路径上所有祖先懒标记复合后的变换，
  需要在访问当前区间时应用。
  本函数采用路径复制，只修改必要的节点，保留未修改部分。
*/
int change(int p, int L, int R, int l, int r, LL b, LL c, LL prop_b, LL prop_c) {
    // 完全不相交：克隆当前节点并应用祖先变换，然后返回
    if (r < L || R < l) {
        int np = clone_node(p);
        modify(np, prop_b, prop_c, R - L + 1);
        return np;
    }
    // 完全覆盖：克隆当前节点，整体施加 “祖先变换 + 当前变换”
    if (l <= L && R <= r) {
        auto t = compose(b, c, prop_b, prop_c); // 先 prop，后 (b,c)
        int np = clone_node(p);
        modify(np, t.first, t.second, R - L + 1);
        return np;
    }
 
    // 部分重叠：创建新节点，懒标记为恒等
    int np = newd();
    // 传递给子节点的祖先变换 = prop ∘ p.lazy（先 p.lazy，后 prop）
    auto t = compose(prop_b, prop_c, tr[p].lazy_b, tr[p].lazy_c);
 
    // 左子区间有重叠，递归处理
    if (l <= MID) {
        lc(np) = change(lc(p), L, MID, l, r, b, c, t.first, t.second);
    } 
    else {
        // 左子区间没有重叠，克隆并应用祖先变换
        if (lc(p) != 0) {
            int lc = clone_node(lc(p));
            modify(lc, t.first, t.second, MID - L + 1);
            lc(np) = lc;
        }
    }
 
    // 右子区间有重叠，递归处理
    if (r >= MID + 1) {
        rc(np) = change(rc(p), MID + 1, R, l, r, b, c, t.first, t.second);
    } 
    else {
        if (rc(p) != 0) {
            int rc = clone_node(rc(p));
            modify(rc, t.first, t.second, R - (MID + 1) + 1);
            rc(np) = rc;
        }
    }
 
    pushup(np);
    return np;
}
 
// 封装 update - change，初始祖先变换为恒等
int update(int p, int L, int R, int l, int r, LL b, LL c) {
    return change(p, L, R, l, r, b, c, 1, 0);
}
 
/*
  合并两个版本 x 和 y，返回一个新版本，其前 at 个元素来自 x，后 len - at 个元素来自 y。
  参数 xb,xc 和 yb,yc 分别为两个版本当前需要应用的祖先变换。
  具体规则：
    - at <= 0         ：全部取 y
    - at >= len       ：全部取 x
    - 否则根据 at 与左子树长度的关系递归处理左右子树。
*/
int crossover(int x, int y, int len, int at, LL xb, LL xc, LL yb, LL yc) {
    if (at <= 0) {                     // 全部来自 y
        if (y == 0) return 0;
        int ny = clone_node(y);
        modify(ny, yb, yc, len);
        return ny;
    }
    if (len <= at) {                   // 全部来自 x
        if (x == 0) return 0;
        int nx = clone_node(x);
        modify(nx, xb, xc, len);
        return nx;
    }
 
    int midl = (len + 1) >> 1;         // 左子树长度（尽量平衡）
    // 为啥是上取整？len = R - L + 1
    // MID = (R + L) / 2
    // midl = MID - L + 1
    // 2 * midl = R + L - 2 * L + 2 * 1
    // midl = R - L + 1
    LL nx_b, nx_c, ny_b, ny_c;
 
    // 将 x 的祖先变换与其自身懒标记复合，得到传递给左/右子树的变换
    if (x != 0) {
        auto res = compose(xb, xc, tr[x].lazy_b, tr[x].lazy_c);
        nx_b = res.first; nx_c = res.second;
    } 
    else {
        nx_b = xb; nx_c = xc;
    }
    if (y != 0) {
        auto res = compose(yb, yc, tr[y].lazy_b, tr[y].lazy_c);
        ny_b = res.first; ny_c = res.second;
    } 
    else {
        ny_b = yb; ny_c = yc;
    }
 
    int left_x = (x == 0) ? 0 : lc(x);
    int left_y = (y == 0) ? 0 : lc(y);
    int right_x = (x == 0) ? 0 : rc(x);
    int right_y = (y == 0) ? 0 : rc(y);
 
    // 左子树需要的前 at 个元素来自 x
    int lc = crossover(left_x, left_y, midl, at,
                       nx_b, nx_c, ny_b, ny_c);
    // 右子树需要的前 at - midl 个元素来自 x
    int rc = crossover(right_x, right_y, len - midl, at - midl,
                       nx_b, nx_c, ny_b, ny_c);
 
    int res = newd();
    lc(res) = lc;
    rc(res) = rc;
    pushup(res);
    return res;
}
 
/*
  操作 1 的封装：将版本 y 的区间 [l, r] 复制到版本 x 的对应位置。
  通过两次交叉实现：
    1. tmp = x[0 : l - 1] + y[l : n]
    2. 结果 = tmp[0 : r] + x[r : n]  = x[0 : l - 1] + y[l : r] + x[r : n]
*/
int update_crossover_twice(int x, int y, int l, int r, int total_len) {
    int tmp = crossover(x, y, total_len, l - 1, 1, 0, 1, 0);
    return crossover(tmp, x, total_len, r, 1, 0, 1, 0);
}
 
/*
  查询版本 p 中区间 [l, r] 的和。
  参数 b, c 表示当前路径上所有祖先懒标记复合后的变换，
  在完全覆盖时直接应用到当前节点的 sum 上。
*/
LL query(int p, int L, int R, int l, int r, LL b, LL c) {
    if (r < L || R < l) {
        return 0;
    }
    if (l <= L && R <= r) {
        return (b * tr[p].sum + c * (R - L + 1)) % P;
    }
 
    // 传递给子节点的祖先变换 = (b,c) ∘ p.lazy（先 p.lazy，后当前祖先）
    auto t = compose(b, c, tr[p].lazy_b, tr[p].lazy_c);
    LL res = 0;
    res += query(lc(p), L, MID, l, r, t.first, t.second);
    res += query(rc(p), MID + 1, R, l, r, t.first, t.second);
    return res % P;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, Q;
    cin >> n >> Q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
 
    tr.reserve(20000000);   // 预留节点空间
    tr.push_back({0, 0, 0, 1, 0});   // 0 号节点作为空节点
 
    int rt;
    build(rt, 1, n);
    vector<int> roots(Q + 1);        // roots[i] 存储版本 A_i 的根节点
    roots[0] = rt;                   // 初始版本 A_{-1}
 
    for (int i = 1; i <= Q; i++) {
        int opt;
        cin >> opt;
 
        // 输入中 k, s 为 0‑based 版本编号，-1 表示初始版本，所以用 k+1 索引 roots
        if (opt == 0) {              // 区间仿射变换
            int k, l, r;
            LL b, c;
            cin >> k >> l >> r >> b >> c;
            l ++;                     // 输入区间为 [l, r) 的 0‑based 下标，转为 1‑based
            int src = roots[k + 1];
            roots[i] = update(src, 1, n, l, r, b, c);
        } 
        else if (opt == 1) {       // 区间从另一版本复制
            int k, s, l, r;
            cin >> k >> s >> l >> r;
            l ++;
            int src_k = roots[k + 1];
            int src_s = roots[s + 1];
            roots[i] = update_crossover_twice(src_k, src_s, l, r, n);
        } 
        else {                     // 区间求和查询
            int k, l, r;
            cin >> k >> l >> r;
            l ++;
            int src = roots[k + 1];
            cout << query(src, 1, n, l, r, 1, 0) << "\n";
            roots[i] = roots[i - 1];
        }
    }
    return 0;
}

哪个小馋猫这么爱吃

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <array>

#include <utility>

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const noexcept { return x; }
    my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; }
    my_type pow(unsigned long long i) const noexcept {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const noexcept { return x; }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia

namespace nachia {

template<
    class S,
    class F,
    S op(S l, S r),
    F composition(F f, F x),
    S mapping(F f, S x)
>
struct PersistentLazySegtree {
public:
    struct Node {
        int l;
        int r;
        S a;
        F f;
    };
    struct Agent{
    public:
        Agent(){}
        Agent(int _sz, int _root, PersistentLazySegtree* _q) : sz(_sz), root(_root), q(_q) {}
        int size() const { return sz; }
        Agent set(int at, S x) const { return copy(q->set(root,sz,at,x,q->id)); }
        S prod(int l, int r) const { return q->prod(root,sz,l,r,q->id); }
        Agent apply(int l, int r, F f) const { return copy(q->apply(root,sz,l,r,f,q->id)); }
        Agent crossover(Agent right, int p) const {
            return copy(q->crossover(root, right.root, sz, p, q->id, q->id));
        }
    private:
        int sz;
        int root;
        PersistentLazySegtree* q = nullptr;
        Agent copy(int newRoot) const { return Agent(sz, newRoot, q); }
    };

    PersistentLazySegtree(){}

    PersistentLazySegtree(S _e, F _id, int reserved_size = 0)
        : e(_e), id(_id) { v.reserve(reserved_size); }

    Agent construct(const std::vector<S>& val){
        return { int(val.size()), fromRange(val.begin(), int(val.size())), this };
    }

private:
    int newLeaf(S x){
        int res = v.size();
        v.push_back({ -1, -1, x, id });
        return res;
    }
    int newMid(int l, int r){
        int res = v.size();
        v.push_back({ l, r, op(v[l].a, v[r].a), id });
        return res;
    }
    int applyAtNode(int p, F f){
        if(v[p].l == -1) return newLeaf(mapping(f, v[p].a));
        int res = v.size();
        v.push_back({ v[p].l, v[p].r, mapping(f, v[p].a), composition(f, v[p].f) });
        return res;
    }
    int set(int p, int n, int at, S x, F prop){
        if(n == 1) return newLeaf(x);
        int m = n / 2;
        auto nxf = composition(prop, v[p].f);
        if(at < m) return newMid(set(v[p].l, m, at, x, nxf), applyAtNode(v[p].r, nxf));
        return newMid(applyAtNode(v[p].l, nxf), set(v[p].r, n-m, at-m, x, nxf));
    }
    S prod(int p, int n, int l, int r, F prop){
        if(l <= 0 && n <= r) return mapping(prop, v[p].a);
        if(r <= 0 || n <= l) return e;
        int m = n / 2;
        auto nxf = composition(prop, v[p].f);
        return op(
            prod(v[p].l, m, l, r, nxf),
            prod(v[p].r, n-m, l-m, r-m, nxf)
        );
    }
    int apply(int p, int n, int l, int r, F f, F prop){
        if(l <= 0 && n <= r) return applyAtNode(p, composition(f, prop));
        if(r <= 0 || n <= l) return applyAtNode(p, prop);
        int m = n / 2;
        auto nxf = composition(prop, v[p].f);
        int l2 = apply(v[p].l, m, l, r, f, nxf);
        int r2 = apply(v[p].r, n-m, l-m, r-m, f, nxf);
        return newMid(l2, r2);
    }
    int crossover(int p, int q, int n, int at, F propl, F propr){
        if(at <= 0) return applyAtNode(q, propr);
        if(n <= at) return applyAtNode(p, propl);
        int m = n / 2;
        auto nxfl = composition(propl, v[p].f);
        auto nxfr = composition(propr, v[q].f);
        int l2 = crossover(v[p].l, v[q].l, m, at, nxfl, nxfr);
        int r2 = crossover(v[p].r, v[q].r, n-m, at-m, nxfl, nxfr);
        return newMid(l2, r2);
    }
    int fromRange(typename std::vector<S>::const_iterator a, int n){
        if(n == 1) return newLeaf(a[0]);
        int m = n / 2;
        return newMid(fromRange(a, m), fromRange(a+m, n-m));
    }

    S e;
    F id;
    std::vector<Node> v;
};

} // namespace nachia

template<class T, int sz>
struct ValArrayOverRing {
    using X = ValArrayOverRing;
    std::array<T, sz> m;
    T& operator[](int i){ return m[i]; }
    const T& operator[](int i) const { return m[i]; }
    X& operator+=(const X& r){ for(int i=0; i<sz; i++){ m[i] += r[i]; } return *this; }
    X& operator-=(const X& r){ for(int i=0; i<sz; i++){ m[i] -= r[i]; } return *this; }
    X& operator*=(const X& r){ for(int i=0; i<sz; i++){ m[i] *= r[i]; } return *this; }
    X operator+(const X& r) const { X p = *this; p += r; return p; }
    X operator-(const X& r) const { X p = *this; p -= r; return p; }
    X operator*(const X& r) const { X p = *this; p *= r; return p; }
};

namespace nachia {

template<class Value>
struct Affine{
    using X = ValArrayOverRing<Value, 2>;
    Value a;
    Value b;
    static Affine Id(){ return { Value(1), Value(0) }; }
    Affine operator()(const Affine& x) const { return { a * x.a, a * x.b + b }; }
    X operator()(const X& x) const { return { x[0], a * x[1] + b * x[0] }; }
    Affine operator+(const Affine& r) const { return { a + r.a, b + r.b }; }
    Affine operator-(const Affine& r) const { return { a - r.a, b - r.b }; }
    Affine& operator+=(const Affine& r) const { a += r.a; b += r.b; return *this; }
    Affine& operator-=(const Affine& r) const { a -= r.a; b -= r.b; return *this; }
};

} // namespace nachia


using namespace std;

using Modint = nachia::StaticModint<998244353>;
using Affine = nachia::Affine<Modint>;
using Value = Affine::X;
Value op(Value l, Value r){ return l + r; }
Value mapping(Affine f, Value x){ return f(x); }
Affine composition(Affine f, Affine x){ return f(x); }

vector<int> solve(int N, int Q, const vector<int>& A, const vector<array<int,6>>& queries){
    using Ds = nachia::PersistentLazySegtree<Value, Affine, op, composition, mapping>;
    Ds ds(Value(), Affine::Id());
    vector<Ds::Agent> data(Q+1);
    vector<Value> mA(N);
    for(int i=0; i<N; i++) mA[i] = { 1, A[i] };
    data[0] = ds.construct(mA);
    vector<int> ans;
    for(int qi=1; qi<=Q; qi++){
        auto& q = queries[qi-1];
        if(q[0] == 0){
            auto [dum0, t, l, r, c, d] = q; t++;
            Modint cm = c;
            Modint dm = d;
            data[qi] = data[t].apply(l, r, {cm,dm});
        }
        else if(q[0] == 1){
            auto [dum0, t, s, l, r, dum1] = q; t++; s++;
            data[qi] = data[t].crossover(data[s], l).crossover(data[t], r);
        }
        else if(q[0] == 2){
            auto [dum0, t, l, r, dum1, dum2] = q; t++;
            Modint v = data[t].prod(l, r)[1];
            ans.push_back(int(v.val()));
        }
    }
    return ans;
}


int main(){
    int N, Q; scanf("%d%d", &N, &Q);
    vector<int> A(N);
    for(auto& a : A) scanf("%d", &a);
    vector<array<int, 6>> queries(Q);
    for(auto& q : queries){
        scanf("%d", &q[0]);
        if(q[0] == 0){
            scanf("%d%d%d%d%d", &q[1], &q[2], &q[3], &q[4], &q[5]);
        } else if(q[0] == 1){
            scanf("%d%d%d%d", &q[1], &q[2], &q[3], &q[4]);
            q[5] = 0;
        } else if(q[0] == 2){
            scanf("%d%d%d", &q[1], &q[2], &q[3]);
            q[4] = q[5] = 0;
        } else exit(1);
    }
    auto ans = solve(N, Q, A, queries);
    for(auto a : ans) printf("%d\n", a);
    return 0;
}