test/library-checker/DataStructure/RangeAffineRangeSum.test.cpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Problem: https://judge.yosupo.jp/problem/range_affine_range_sum

Depends on

• build/pch/stdc++.hpp
• library/algebra/group/Affine.hpp
• library/algebra/group/CntSum.hpp
• library/algebra/lazy/AffineSum.hpp
• library/linearalgebra/Linear.hpp
• library/math/ExtraGCD.hpp
• library/mod/Modint.hpp
• library/segtree/LazySegmentTree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <bits/stdc++.h>

#include "library/algebra/lazy/AffineSum.hpp"
#include "library/mod/Modint.hpp"
#include "library/segtree/LazySegmentTree.hpp"

using mint = Mint<long long>;

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

    int n, q;
    std::cin >> n >> q;

    std::vector<mint> v(n);
    for (int i = 0; i < n; i++)
        std::cin >> v[i];
    LazySegmentTree<LazyAffineSum<mint>> seg(cnt_init(v));

    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        if (t)
            std::cout << seg.prod(l, r).first << '\n';
        else {
            Line<mint> f;
            std::cin >> f;
            seg.apply(l, r, f);
        }
    }
}

#line 1 "test/library-checker/DataStructure/RangeAffineRangeSum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include <bits/stdc++.h>

#line 2 "library/linearalgebra/Linear.hpp"
template <typename T> struct Line {
    T a, b;
    Line() = default;
    Line(T a, T b) : a(a), b(b) {}
    Line(std::pair<T, T> l) : a(l.first), b(l.second) {}
    Line(T c) : a(0), b(c) {}

    T operator()(const T x) const { return a * x + b; }
    Line operator()(const Line &l) const { return Line(a * l.a, a * l.b + b); }

    bool operator==(const Line &l) const { return a == l.a and b == l.b; }
    bool operator!=(const Line &l) const { return !(*this == l); }
    bool operator<(const Line &l) const {
        return (a == l.a ? a < l.a : b < l.b);
    }

    Line &operator+=(const Line &l) {
        a += l.a;
        b += l.b;
        return *this;
    }
    Line operator+(const Line &l) const { return Line(*this) += l; }
    Line &operator-=(const Line &l) {
        a -= l.a;
        b -= l.b;
        return *this;
    }
    Line operator-(const Line &l) const { return Line(*this) -= l; }
    Line operator-() const { return Line(-a, -b); }

    Line &operator+=(const T &c) {
        b += c;
        return *this;
    }
    Line operator+(const T &c) const { return Line(*this) += c; }
    Line &operator-=(const T &c) {
        b -= c;
        return *this;
    }
    Line operator-(const T &c) const { return Line(*this) -= c; }
    Line &operator*=(const T &c) {
        a *= c;
        b *= c;
        return *this;
    }
    Line operator*(const T &c) const { return Line(*this) *= c; }
    Line &operator/=(const T &c) {
        a /= c;
        b /= c;
        return *this;
    }
    Line operator/(const T &c) const { return Line(*this) /= c; }

    Line inv() const {
        assert(a != 0);
        return Line(T(1) / a, -b / a);
    }

    friend std::istream &operator>>(std::istream &is, Line &l) {
        is >> l.a >> l.b;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Line &l) {
        if (l.a == 0 and l.b == 0)
            os << 0;
        else if (l.a == 0)
            os << l.b;
        else if (l.b == 0)
            os << l.a << "x";
        else if (l.b > 0)
            os << l.a << "x+" << l.b;
        else
            os << l.a << "x-" << -l.b;
        return os;
    }
};
#line 3 "library/algebra/group/Affine.hpp"
template <typename T> struct GroupAffine {
    using L = Line<T>;
    using value_type = L;
    static constexpr L op(const L &f, const L &g) noexcept { return f(g); }
    static constexpr void Rchop(L &f, const L &g) {
        f.b += f.a * g.b;
        f.a *= g.a;
    }
    static constexpr void Lchop(const L &f, L &g) {
        (g.b *= f.a) += f.b;
        g.a *= f.a;
    }
    static constexpr L inverse(const L &f) { return f.inv(); }
    /*
    static constexpr L power(const L& f,long long n) noexcept {
      if(a==1)return {1,n*b};
      K an=power(a,n);
      return {an,b*((1-an)/(1-a))};
    }
    */
    static constexpr L unit() { return L(1, 0); }
    static constexpr bool commute = false;
};
#line 1 "library/algebra/group/CntSum.hpp"
template <typename X> struct GroupCntSum {
    using P = std::pair<X, X>;
    using value_type = P;
    static constexpr P op(const P &x, const P &y) {
        return {x.first + y.first, x.second + y.second};
    }
    static constexpr void Rchop(P &x, const P &y) {
        x.first += y.first;
        x.second += y.second;
    }
    static constexpr void Lchop(const P &x, P &y) {
        y.first += x.first;
        y.second += x.second;
    }
    static constexpr P inverse(const P &x) { return {-x.fi, -x.se}; }
    static constexpr P unit() { return {0, 0}; }
    static constexpr bool commute = true;
};
template <typename X> std::vector<std::pair<X, X>> cnt_init(int n, const X &x) {
    return std::vector<std::pair<X, X>>(n, {x, 1});
}
template <typename X>
std::vector<std::pair<X, X>> cnt_init(const std::vector<X> &v) {
    int n = v.size();
    std::vector<std::pair<X, X>> res(n);
    for (int i = 0; i < n; i++)
        res[i] = {v[i], 1};
    return res;
}
#line 4 "library/algebra/lazy/AffineSum.hpp"
template <typename X> struct LazyAffineSum {
    using MX = GroupCntSum<X>;
    using MF = GroupAffine<X>;
    using P = typename MX::value_type;
    using F = typename MF::value_type;
    static constexpr P mapping(const F &f, const P &x) {
        return {f.a * x.first + f.b * x.second, x.second};
    }
};
#line 2 "library/math/ExtraGCD.hpp"
using ll = long long;
std::pair<ll, ll> ext_gcd(ll a, ll b) {
    if (b == 0)
        return {1, 0};
    auto [X, Y] = ext_gcd(b, a % b);
    // bX + (a%b)Y = gcd(a,b)
    // a%b = a - b(a/b)
    // ∴ aY + b(X-(a/b)Y) = gcd(a,b)
    ll x = Y, y = X - (a / b) * Y;
    return {x, y};
}
#line 3 "library/mod/Modint.hpp"
template <typename T, T MOD = 998244353> struct Mint {
    inline static constexpr T mod = MOD;
    T v;
    Mint() : v(0) {}
    Mint(signed v) : v(v) {}
    Mint(long long t) {
        v = t % MOD;
        if (v < 0)
            v += MOD;
    }

    static Mint raw(int v) {
        Mint x;
        x.v = v;
        return x;
    }

    Mint pow(long long k) const {
        Mint res(1), tmp(v);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }

    static Mint add_identity() { return Mint(0); }
    static Mint mul_identity() { return Mint(1); }

    // Mint inv()const{return pow(MOD-2);}
    Mint inv() const { return Mint(ext_gcd(v, mod).first); }

    Mint &operator+=(Mint a) {
        v += a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator-=(Mint a) {
        v += MOD - a.v;
        if (v >= MOD)
            v -= MOD;
        return *this;
    }
    Mint &operator*=(Mint a) {
        v = 1LL * v * a.v % MOD;
        return *this;
    }
    Mint &operator/=(Mint a) { return (*this) *= a.inv(); }

    Mint operator+(Mint a) const { return Mint(v) += a; }
    Mint operator-(Mint a) const { return Mint(v) -= a; }
    Mint operator*(Mint a) const { return Mint(v) *= a; }
    Mint operator/(Mint a) const { return Mint(v) /= a; }
#define FRIEND(op)                                                             \
    friend Mint operator op(int a, Mint b) { return Mint(a) op b; }
    FRIEND(+);
    FRIEND(-);
    FRIEND(*);
    FRIEND(/);
#undef FRIEND
    Mint operator+() const { return *this; }
    Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); }

    bool operator==(const Mint a) const { return v == a.v; }
    bool operator!=(const Mint a) const { return v != a.v; }

    static Mint comb(long long n, int k) {
        Mint num(1), dom(1);
        for (int i = 0; i < k; i++) {
            num *= Mint(n - i);
            dom *= Mint(i + 1);
        }
        return num / dom;
    }

    friend std::ostream &operator<<(std::ostream &os, const Mint &m) {
        os << m.v;
        return os;
    }
    friend std::istream &operator>>(std::istream &is, Mint &m) {
        is >> m.v;
        m.v %= MOD;
        if (m.v < 0)
            m.v += MOD;
        return is;
    }
};
#line 2 "library/segtree/LazySegmentTree.hpp"

template <typename Lazy> class LazySegmentTree {
    using MX = typename Lazy::MX;
    using MF = typename Lazy::MF;
    using X = typename MX::value_type;
    using F = typename MF::value_type;
    int n, log, size;
    std::vector<X> dat;
    std::vector<F> laz;

    X reflect(int k) {
        if (k < size)
            return Lazy::mapping(laz[k], dat[k]);
        return dat[k];
    }
    void point_apply(int k, const F &f) {
        if (k < size)
            MF::Lchop(f, laz[k]);
        else
            dat[k] = Lazy::mapping(f, dat[k]);
    }
    void push(int k) {
        dat[k] = reflect(k);
        point_apply(2 * k, laz[k]);
        point_apply(2 * k + 1, laz[k]);
        laz[k] = MF::unit();
    }
    void thrust(int k) {
        for (int i = log; i; i--)
            push(k >> i);
    }
    void update(int i) { dat[i] = MX::op(reflect(2 * i), reflect(2 * i + 1)); }
    void recalc(int k) {
        while (k >>= 1)
            update(k);
    }

  public:
    LazySegmentTree() : LazySegmentTree(0) {}
    LazySegmentTree(int n) : LazySegmentTree(std::vector<X>(n, MX::unit())) {}
    LazySegmentTree(const std::vector<X> &v) : n(v.size()) {
        for (log = 1; (1 << log) < n; log++) {
        }
        size = 1 << log;
        dat.assign(size << 1, MX::unit());
        laz.assign(size, MF::unit());
        for (int i = 0; i < n; ++i)
            dat[size + i] = v[i];
        for (int i = size - 1; i >= 1; --i)
            update(i);
    }

    void set(int p, X x) {
        assert(0 <= p and p < n);
        thrust(p += size);
        dat[p] = x;
        recalc(p);
    }

    X operator[](int p) {
        assert(0 <= p and p < n);
        thrust(p += size);
        return reflect(p);
    }

    X prod(int L, int R) {
        assert(0 <= L and L <= R and R <= n);
        if (L == R)
            return MX::unit();
        thrust(L += size);
        thrust((R += size - 1)++);
        X vl = MX::unit(), vr = MX::unit();
        while (L < R) {
            if (L & 1)
                MX::Rchop(vl, reflect(L++));
            if (R & 1)
                MX::Lchop(reflect(--R), vr);
            L >>= 1, R >>= 1;
        }
        return MX::op(vl, vr);
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r)
            return;
        thrust(l += size);
        thrust(r += size - 1);
        for (int L = l, R = r + 1; L < R; L >>= 1, R >>= 1) {
            if (L & 1)
                point_apply(L++, f);
            if (R & 1)
                point_apply(--R, f);
        }
        recalc(l);
        recalc(r);
    }
};
#line 7 "test/library-checker/DataStructure/RangeAffineRangeSum.test.cpp"

using mint = Mint<long long>;

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

    int n, q;
    std::cin >> n >> q;

    std::vector<mint> v(n);
    for (int i = 0; i < n; i++)
        std::cin >> v[i];
    LazySegmentTree<LazyAffineSum<mint>> seg(cnt_init(v));

    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        if (t)
            std::cout << seg.prod(l, r).first << '\n';
        else {
            Line<mint> f;
            std::cin >> f;
            seg.apply(l, r, f);
        }
    }
}

Back to top page