verify/LC-RangeAffineRangeSum.test.cpp

• View this file on GitHub
• Last update: 2026-02-12 01:36:24+09:00
• Problem: https://judge.yosupo.jp/problem/range_affine_range_sum

Depends on

• Library/Common.hpp
• Lazy Segment Tree - 遅延評価セグメント木 (Library/DataStructure/LazySegmentTree.hpp)
• Template - ユーティリティ関数群 (Library/Template.hpp)
• modint (Library/modint.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"

#include "../Library/Template.hpp"
#include "../Library/modint.hpp"
#include "../Library/DataStructure/LazySegmentTree.hpp"

struct Monoid{
    mint a;
    int len;
    Monoid(mint a_ = 0, int len_ = 1) : a(a_), len(len_){}
    static Monoid Merge(Monoid &l, Monoid &r){
        return Monoid(l.a + r.a, l.len + r.len);
    }
};

struct OperatorMonoid{
    mint b, c;
    OperatorMonoid(mint b_ = 1, mint c_ = 0) : b(b_), c(c_){}
    static Monoid Mapping(Monoid &m, OperatorMonoid &op){
        return Monoid(op.b * m.a + op.c * m.len, m.len);
    }
    static OperatorMonoid Composite(OperatorMonoid &l, OperatorMonoid &r){
        return OperatorMonoid(r.b * l.b, r.b * l.c + r.c);
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    vector<Monoid> A(N);
    for(int i = 0; i < N; ++i){
        mint a; cin >> a;
        A[i] = Monoid(a);
    }

    LazySegmentTree<Monoid, OperatorMonoid> seg(A,
        [](Monoid l, Monoid r){return Monoid::Merge(l, r);},
        [](Monoid m, OperatorMonoid op){return OperatorMonoid::Mapping(m, op);},
        [](OperatorMonoid l, OperatorMonoid r){return OperatorMonoid::Composite(l, r);},
        Monoid(),
        OperatorMonoid(),
        true);
    while(Q--){
        int t; cin >> t;
        if(t == 0){
            int l, r, b, c; cin >> l >> r >> b >> c;
            seg.Apply(l, r, OperatorMonoid(b, c));
        }
        else{
            int l, r; cin >> l >> r;
            cout << seg.Fold(l, r).a << '\n';
        }
    }
}

#line 1 "verify/LC-RangeAffineRangeSum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"

#line 2 "Library/Template.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/Template.hpp"

inline bool YnPrint(bool flag){cout << (flag ? "Yes" : "No") << '\n'; return flag;}
inline bool YNPrint(bool flag){cout << (flag ? "YES" : "NO") << '\n'; return flag;}
template<typename Container>
inline void Sort(Container &container){sort(container.begin(), container.end());}
template<typename Container>
inline void ReverseSort(Container &container){sort(container.rbegin(), container.rend());}
template<typename Container>
inline void Reverse(Container &container){reverse(container.begin(), container.end());}
template<typename Value>
inline int PopCount(const Value &value){return __builtin_popcount(value);}
template<typename Value>
inline Value Floor(Value numerator, Value denominator){if(denominator < 0) numerator *= -1, denominator *= -1; return numerator < 0 ? (numerator + 1) / denominator - 1 : numerator / denominator;}
template<typename Value>
inline Value Ceil(Value numerator, Value denominator){if(denominator < 0) numerator *= -1, denominator *= -1; return numerator > 0 ? (numerator - 1) / denominator + 1 : numerator / denominator;}
template<typename Value>
inline int LowerBoundIndex(const vector<Value> &container, const Value &value){return distance(container.begin(), lower_bound(container.begin(), container.end(), value));}
template<typename Value>
inline int UpperBoundIndex(const vector<Value> &container, const Value &value){return distance(container.begin(), upper_bound(container.begin(), container.end(), value));}
template<typename Value>
inline bool Between(const Value &lower, const Value &x, const Value &higher){return lower <= x && x <= higher;}
template<typename Value>
inline bool InGrid(const Value &y, const Value &x, const Value &ymax, const Value &xmax){return Between(0, y, ymax - 1) && Between(0, x, xmax - 1);}
template<typename Value>
inline Value Median(const Value &a, const Value &b, const Value &c){return Between(b, a, c) || Between(c, a, b) ? a : (Between(a, b, c) || Between(c, b, a) ? b : c);}
template<typename Value>
inline Value Except(Value &src, Value &cond, Value &excp){return (src == cond ? excp : src);}

template<class Value>
bool chmin(Value &src, const Value &cmp){if(src > cmp){src = cmp; return true;} return false;}
template<class Value>
bool chmax(Value &src, const Value &cmp){if(src < cmp){src = cmp; return true;} return false;}
template<typename Value>
inline Value min(vector<Value> &v){return *min_element((v).begin(), (v).end());}
template<typename Value>
inline Value max(vector<Value> &v){return *max_element((v).begin(), (v).end());}

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, -1, 0, 1};
const int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy8[8] = {0, -1, -1, -1, 0, 1, 1, 1};

vector<pair<int, int>> adjacent(int current_y, int current_x, int max_y, int max_x, bool dir_8 = false){
    vector<pair<int, int>> ret;
    for(int d = 0; d < 4 * (1 + dir_8); ++d){
        int next_y = current_y + (dir_8 ? dy8[d] : dy4[d]);
        int next_x = current_x + (dir_8 ? dx8[d] : dx4[d]);
        if(InGrid(next_y, next_x, max_y, max_x)){
            ret.emplace_back(next_y, next_x);
        }
    }
    return ret;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p){
    os << p.first << " " << p.second;
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p){
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v){
    for (int i = 0; i < v.size(); ++i){
        os << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &v){
    for (int i = 0; i < v.size(); ++i){
        os << v[i] << (i + 1 != v.size() ? "\n" : "");
    }
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (int i = 0; i < v.size(); ++i) is >> v[i];
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, set<T> &v){
    for (auto &u : v){
        os << u << " ";
    }
    return os;
}

template<typename T1, typename T2>
vector<pair<T1, T2>> AssembleVectorPair(vector<T1> &v1, vector<T2> &v2){
    assert(v1.size() == v2.size());
    vector<pair<T1, T2>> v;
    for(int i = 0; i < v1.size(); ++i) v.push_back({v1[i], v2[i]});
    return v;
}

template<typename T1, typename T2>
pair<vector<T1>, vector<T2>> DisassembleVectorPair(vector<pair<T1, T2>> &v){
    vector<T1> v1;
    vector<T2> v2;
    transform(v.begin(), v.end(), back_inserter(v1), [](auto p){return p.first;});
    transform(v.begin(), v.end(), back_inserter(v2), [](auto p){return p.second;});
    return {v1, v2};
}

template<typename T1, typename T2, typename T3>
tuple<vector<T1>, vector<T2>, vector<T3>> DisassembleVectorTuple(vector<tuple<T1, T2, T3>> &v){
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    transform(v.begin(), v.end(), back_inserter(v1), [](auto p){return get<0>(p);});
    transform(v.begin(), v.end(), back_inserter(v2), [](auto p){return get<1>(p);});
    transform(v.begin(), v.end(), back_inserter(v3), [](auto p){return get<2>(p);});
    return {v1, v2, v3};
}

template<typename T1 = int, typename T2 = T1>
pair<vector<T1>, vector<T2>> InputVectorPair(int size){
    vector<pair<T1, T2>> v(size);
    for(auto &[p, q] : v) cin >> p >> q;
    return DisassembleVectorPair(v);
}

template<typename T1 = int, typename T2 = T1, typename T3 = T1>
tuple<vector<T1>, vector<T2>, vector<T3>> InputVectorTuple(int size){
    vector<tuple<T1, T2, T3>> v(size);
    for(auto &[p, q, r] : v) cin >> p >> q >> r;
    return DisassembleVectorTuple(v);
}
#line 2 "Library/modint.hpp"

/**
 * @file modint.hpp
 * @author log K (lX57)
 * @brief modint
 * @version 1.0
 * @date 2023-08-24
 */

#line 12 "Library/modint.hpp"
using namespace std;

const int mod998 = 998244353;
const int mod107 = 1000000007;

template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        if(n == 0) return ModInt(1);
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using mint = ModInt<mod998>;
using mint107 = ModInt<mod107>;

using vm = vector<mint>;
using vvm = vector<vector<mint>>;
using vm107 = vector<mint107>;
using vvm107 = vector<vector<mint107>>;
#line 2 "Library/DataStructure/LazySegmentTree.hpp"

template<typename Monoid, typename OperatorMonoid = Monoid>
class LazySegmentTree{
    public:
    using F = function<Monoid(Monoid, Monoid)>;
    using G = function<Monoid(Monoid, OperatorMonoid)>;
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;

    LazySegmentTree(
        vector<Monoid> &A,
        F merge,
        G mapping,
        H composite,
        const Monoid &e_m,
        const OperatorMonoid &e_o,
        bool zero_index = false
    ) : f(merge), g(mapping), h(composite), m1_(e_m), om1_(e_o), zero_index_(zero_index){
        size_ = 1;
        while(size_ < (int)A.size()) size_ <<= 1;
        offset_ = size_ - 1;
        data_.resize(2 * size_, m1_);
        lazy_.resize(2 * size_, om1_);
        is_identity_.resize(2 * size_, true);
        for(int i = 0; i < (int)A.size(); ++i){
            data_[size_ + i] = A[i];
        }
        for(int i = offset_; i >= 1; --i){
            data_[i] = f(data_[i * 2 + 0], data_[i * 2 + 1]);
        }
    }

    void Apply(int l, int r, OperatorMonoid x){
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        RecursiveApply(l + zero_index_, r + zero_index_, x, 1, size_ + 1, 1);
    }

    Monoid Fold(int l, int r){
        Validate(l + zero_index_);
        Validate(r + zero_index_ - 1);
        return RecursiveFold(l + zero_index_, r + zero_index_, 1, size_ + 1, 1);
    }

    Monoid operator[](const int &k){
        Validate(k + zero_index_);
        return Fold(k, k + 1);
    }

    private:
    int size_, offset_, zero_index_;
    vector<Monoid> data_;
    vector<OperatorMonoid> lazy_;
    vector<bool> is_identity_;
    const F f;
    const G g;
    const H h;
    const Monoid m1_;
    const OperatorMonoid om1_;

    inline void Validate(int x){
        assert(1 <= x && x <= size_);
    }

    void Evaluate(int k){
        if(is_identity_[k]) return;
        if(k < size_){
            lazy_[k * 2 + 0] = h(lazy_[k * 2 + 0], lazy_[k]);
            is_identity_[k * 2 + 0] = false;
            lazy_[k * 2 + 1] = h(lazy_[k * 2 + 1], lazy_[k]);
            is_identity_[k * 2 + 1] = false;
        }
        data_[k] = g(data_[k], lazy_[k]);
        lazy_[k] = om1_;
        is_identity_[k] = true;
    }

    void RecursiveApply(int ul, int ur, OperatorMonoid x, int left, int right, int cell){
        Evaluate(cell);
        if(ul <= left && right <= ur){
            lazy_[cell] = h(lazy_[cell], x);
            is_identity_[cell] = false;
            Evaluate(cell);
        }
        else if(ul < right && left < ur){
            int mid = (left + right) / 2;
            RecursiveApply(ul, ur, x, left, mid, cell * 2 + 0);
            RecursiveApply(ul, ur, x, mid, right, cell * 2 + 1);
            data_[cell] = f(data_[cell * 2 + 0], data_[cell * 2 + 1]);
        }
    }

    Monoid RecursiveFold(int ql, int qr, int left, int right, int cell){
        Evaluate(cell);
        if(qr <= left || right <= ql){
            return m1_;
        }
        if(ql <= left && right <= qr){
            return data_[cell];
        }
        int mid = (left + right) / 2;
        Monoid ans_left = RecursiveFold(ql, qr, left, mid, cell * 2 + 0);
        Monoid ans_right = RecursiveFold(ql, qr, mid, right, cell * 2 + 1);
        return f(ans_left, ans_right);
    }
};
#line 6 "verify/LC-RangeAffineRangeSum.test.cpp"

struct Monoid{
    mint a;
    int len;
    Monoid(mint a_ = 0, int len_ = 1) : a(a_), len(len_){}
    static Monoid Merge(Monoid &l, Monoid &r){
        return Monoid(l.a + r.a, l.len + r.len);
    }
};

struct OperatorMonoid{
    mint b, c;
    OperatorMonoid(mint b_ = 1, mint c_ = 0) : b(b_), c(c_){}
    static Monoid Mapping(Monoid &m, OperatorMonoid &op){
        return Monoid(op.b * m.a + op.c * m.len, m.len);
    }
    static OperatorMonoid Composite(OperatorMonoid &l, OperatorMonoid &r){
        return OperatorMonoid(r.b * l.b, r.b * l.c + r.c);
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    vector<Monoid> A(N);
    for(int i = 0; i < N; ++i){
        mint a; cin >> a;
        A[i] = Monoid(a);
    }

    LazySegmentTree<Monoid, OperatorMonoid> seg(A,
        [](Monoid l, Monoid r){return Monoid::Merge(l, r);},
        [](Monoid m, OperatorMonoid op){return OperatorMonoid::Mapping(m, op);},
        [](OperatorMonoid l, OperatorMonoid r){return OperatorMonoid::Composite(l, r);},
        Monoid(),
        OperatorMonoid(),
        true);
    while(Q--){
        int t; cin >> t;
        if(t == 0){
            int l, r, b, c; cin >> l >> r >> b >> c;
            seg.Apply(l, r, OperatorMonoid(b, c));
        }
        else{
            int l, r; cin >> l >> r;
            cout << seg.Fold(l, r).a << '\n';
        }
    }
}

Back to top page