verify/yosupo/yosupo_range_affine_range_sum.test.cpp

View this file on GitHub
Last update: 2025-06-19 01:34:37+09:00
Problem: https://judge.yosupo.jp/problem/range_affine_range_sum

Depends on

Code

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

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

#include "../../data_structure/lazy_segmemt_tree.hpp"
#include "../../data_structure/static_modint.hpp"

using mint = StaticModint<998244353>;

using S = pair<mint, mint>;
S op(S l, S r) { return {l.first + r.first, l.second + r.second}; }
S e() { return {0, 0}; }
using F = pair<mint, mint>;
S mapping(F f, S x) { return {x.first * f.first + x.second * f.second, x.second}; }
F composition(F f, F g) { return {f.first * g.first, f.first * g.second + f.second}; }
F id() { return {1, 0}; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    vector<S> A(N);
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        A[i] = {a, 1};
    }

    LazySegmentTree<S, op, e, F, mapping, composition, id> seg(A);

    while(Q--) {
        int q;
        cin >> q;
        if(q == 0) {
            int l, r, b, c;
            cin >> l >> r >> b >> c;
            seg.apply(l, r, {b, c});
        }
        if(q == 1) {
            int l, r;
            cin >> l >> r;
            cout << seg.prod(l, r).first << "\n";
        }
    }

    return 0;
}

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

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

#line 1 "data_structure/lazy_segmemt_tree.hpp"
template<class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct LazySegmentTree{
    int n, log;
    vector<S> data;
    vector<F> lazy;

    LazySegmentTree(int n) : LazySegmentTree(vector<S>(n, e())) {}

    LazySegmentTree(const vector<S> &v) {
        int sz = v.size();
        n = 1; 
        log = 0;
        while(n < sz) {
            n <<= 1;
            log++;
        }

        data.resize(2 * n, e());
        lazy.resize(2 * n, id());

        for(int i = 0; i < sz; i++) data[i + n] = v[i];
        for(int i = n; --i;) data[i] = op(data[i << 1], data[i << 1 | 1]);
    }

    S prod(int l, int r) {
        if(l == r) return e();
        l += n; r += n;

        for(int i = log; i >= 1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push(r >> i);
        }

        S vl = e(), vr = e();
        while(l < r) {
            if(l & 1) vl = op(vl, data[l++]);
            if(r & 1) vr = op(data[--r], vr);
            l >>= 1; r >>= 1;
        }

        return op(vl, vr);
    }

    void apply(int l, int r, F f) {
        if(l == r) return;
        l += n; r += n;
        
        for(int i = log; i >= 1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while(l < r) {
                if(l & 1) all_apply(l++, f);
                if(r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2; r = r2;
        }

        for(int i = 1; i <= log; i++) {
            if(((l >> i) << i) != l) update(l >> i);
            if(((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    inline void update(int k) { data[k] = op(data[k << 1], data[k << 1 | 1]); }
    inline void all_apply(int k, F f) {
        data[k] = mapping(f, data[k]);
        if(k < n) lazy[k] = composition(f, lazy[k]);
    }
    inline void push(int k) {
        all_apply(k << 1, lazy[k]);
        all_apply(k << 1 | 1, lazy[k]);
        lazy[k] = id();
    }
};
#line 1 "data_structure/static_modint.hpp"
template<int m> struct StaticModint {
    using mint = StaticModint;
    int _v;

    constexpr StaticModint() : _v(0) {}
    template<class T>
    constexpr StaticModint(T v) : _v((v % m + m) % m) {}

    constexpr int val() const { return _v; }

    constexpr mint& operator ++ () { return *this += 1; }
    constexpr mint& operator -- () { return *this -= 1; }
    constexpr mint operator ++ (int) { mint res = *this; ++*this; return res; }
    constexpr mint operator -- (int) { mint res = *this; --*this; return res; }

    constexpr mint& operator += (const mint& r) {
        if(_v >= m - r._v) _v -= m;
        _v += r._v; return *this;
    }
    constexpr mint& operator -= (const mint& r) {
        if(_v < r._v) _v += m;
        _v -= r._v; return *this;
    }
    constexpr mint& operator *= (const mint& r) {
        unsigned long long z = _v;
        z *= r._v;
        _v = (unsigned int)(z % m); return *this;
    }
    constexpr mint& operator /= (const mint& r) {
        return *this *= r.inv(); 
    }

    constexpr mint pow(long long n) const {
        mint x = *this, r = 1; 
        while(n) {
            if(n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    constexpr mint inv() const {
        return pow(m - 2);
    }

    constexpr mint operator + () const { return *this; }
    constexpr mint operator - () const { return mint() - *this; }

    constexpr mint operator + (const mint& r) const { return mint(*this) += r; }
    constexpr mint operator - (const mint& r) const { return mint(*this) -= r; }
    constexpr mint operator * (const mint& r) const { return mint(*this) *= r; }
    constexpr mint operator / (const mint& r) const { return mint(*this) /= r; }

    friend constexpr mint operator + (long long l, const mint& r) { return mint(l) + r; }
    friend constexpr mint operator - (long long l, const mint& r) { return mint(l) - r; }
    friend constexpr mint operator * (long long l, const mint& r) { return mint(l) * r; }
    friend constexpr mint operator / (long long l, const mint& r) { return mint(l) / r; }
    
    constexpr bool operator == (const mint& r) const { return _v == r._v; }
    constexpr bool operator != (const mint& r) const { return _v != r._v; }

    friend istream& operator >> (istream& is, mint& x) {
        long long t;
        is >> t;
        x = mint(t);
        return is;
    }
    friend ostream& operator << (ostream& os, const mint& x) {
        return os << x._v;
    }
};

// using mint = StaticModint<998244353>;
// using mint = StaticModint<1000000007>;
#line 8 "verify/yosupo/yosupo_range_affine_range_sum.test.cpp"

using mint = StaticModint<998244353>;

using S = pair<mint, mint>;
S op(S l, S r) { return {l.first + r.first, l.second + r.second}; }
S e() { return {0, 0}; }
using F = pair<mint, mint>;
S mapping(F f, S x) { return {x.first * f.first + x.second * f.second, x.second}; }
F composition(F f, F g) { return {f.first * g.first, f.first * g.second + f.second}; }
F id() { return {1, 0}; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    vector<S> A(N);
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        A[i] = {a, 1};
    }

    LazySegmentTree<S, op, e, F, mapping, composition, id> seg(A);

    while(Q--) {
        int q;
        cin >> q;
        if(q == 0) {
            int l, r, b, c;
            cin >> l >> r >> b >> c;
            seg.apply(l, r, {b, c});
        }
        if(q == 1) {
            int l, r;
            cin >> l >> r;
            cout << seg.prod(l, r).first << "\n";
        }
    }

    return 0;
}