icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/data_structure/Range_Affine_Range_Sum.test.cpp

Depends on

Code

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

#include <iostream>
#include <vector>

#include "../../data_structure/lazysegtree.hpp"
#include "../../template/template.hpp"
#include "../../utility/modint.hpp"

using namespace lib;

using mint = modint998244353;

struct S {
    mint a;
    int size;
};

struct F {
    mint a, b;
    F(mint a, mint b) : a(a), b(b) {}
};

S op(S l, S r) {
    return S{l.a + r.a, l.size + r.size};
}

S e() {
    return S{0, 0};
}

S mapping(F l, S r) {
    return S{r.a * l.a + (mint)r.size * l.b, r.size};
}

F composition(F l, F r) {
    return F{r.a * l.a, r.b * l.a + l.b};
}

F id() {
    return F{1, 0};
}

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<S> v(n);
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        v[i] = {a, 1};
    }
    lazysegtree<S, op, e, F, mapping, composition, id> seg(v);
    while (q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int l, r, b, c;
            std::cin >> l >> r >> b >> c;
            seg.apply(l, r, F(b, c));
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << seg.prod(l, r).a.val() << std::endl;
        }
    }
}
#line 1 "test/data_structure/Range_Affine_Range_Sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"

#include <iostream>
#include <vector>

#line 2 "data_structure/lazysegtree.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/lazysegtree.hpp"

namespace lib {

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
struct lazysegtree {
  private:
    int n, lg2, sz;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int i) {
        d[i] = op(d[2 * i], d[2 * i + 1]);
    }

    void all_apply(int i, F f) {
        d[i] = mapping(f, d[i]);
        if (i < sz) lz[i] = composition(f, lz[i]);
    }

    void push(int i) {
        all_apply(2 * i, lz[i]);
        all_apply(2 * i + 1, lz[i]);
        lz[i] = id();
    }

  public:
    lazysegtree(int _n) : lazysegtree(std::vector<S>(_n, e())) {}

    lazysegtree(const std::vector<S> &v) : n(v.size()) {
        lg2 = 0;
        while ((1 << lg2) < n) lg2++;
        sz = 1 << lg2;
        d = std::vector<S>(2 * sz, e());
        lz = std::vector<F>(2 * sz, id());
        for (int i = 0; i < n; i++) d[sz + i] = v[i];
        for (int i = sz - 1; i >= 1; i--) update(i);
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += sz;
        rrep(i, 1, lg2 + 1) push(p >> i);
        d[p] = x;
        rep(i, 1, lg2 + 1) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < n);
        p += sz;
        rrep(i, 1, lg2 + 1) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return e();
        l += sz;
        r += sz;
        rrep(i, 1, lg2 + 1) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() {
        return d[1];
    }

    void apply(int p, F f) {
        assert(0 <= p && p < n);
        p += sz;
        rrep(i, 1, lg2 + 1) push(p >> i);
        d[p] = mapping(f, d[p]);
        rep(i, 1, lg2 + 1) update(p >> i);
    }

    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return;
        l += sz;
        r += sz;
        rrep(i, 1, lg2 + 1) {
            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;
        }

        rep(i, 1, lg2 + 1) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= n);
        assert(g(e()));
        if (l == n) return n;
        l += sz;
        for (int i = lg2; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < sz) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - sz;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= n);
        assert(g(e()));
        if (r == 0) return 0;
        r += sz;
        for (int i = lg2; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < sz) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

}  // namespace lib
#line 2 "utility/modint.hpp"

#line 4 "utility/modint.hpp"

namespace lib {

template <ll m> struct modint {
    using mint = modint;
    ll a;

    modint(ll x = 0) : a((x % m + m) % m) {}
    static constexpr ll mod() {
        return m;
    }
    ll val() const {
        return a;
    }
    ll& val() {
        return a;
    }
    mint pow(ll n) const {
        mint res = 1;
        mint x = a;
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    mint inv() const {
        return pow(m - 2);
    }
    mint& operator+=(const mint rhs) {
        a += rhs.a;
        if (a >= m) a -= m;
        return *this;
    }
    mint& operator-=(const mint rhs) {
        if (a < rhs.a) a += m;
        a -= rhs.a;
        return *this;
    }
    mint& operator*=(const mint rhs) {
        a = a * rhs.a % m;
        return *this;
    }
    mint& operator/=(mint rhs) {
        *this *= rhs.inv();
        return *this;
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const modint &lhs, const modint &rhs) {
        return lhs.a == rhs.a;
    }
    friend bool operator!=(const modint &lhs, const modint &rhs) {
        return !(lhs == rhs);
    }
    mint operator+() const {
        return *this;
    }
    mint operator-() const {
        return mint() - *this;
    }
};

using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1'000'000'007>;

}  // namespace lib
#line 9 "test/data_structure/Range_Affine_Range_Sum.test.cpp"

using namespace lib;

using mint = modint998244353;

struct S {
    mint a;
    int size;
};

struct F {
    mint a, b;
    F(mint a, mint b) : a(a), b(b) {}
};

S op(S l, S r) {
    return S{l.a + r.a, l.size + r.size};
}

S e() {
    return S{0, 0};
}

S mapping(F l, S r) {
    return S{r.a * l.a + (mint)r.size * l.b, r.size};
}

F composition(F l, F r) {
    return F{r.a * l.a, r.b * l.a + l.b};
}

F id() {
    return F{1, 0};
}

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<S> v(n);
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        v[i] = {a, 1};
    }
    lazysegtree<S, op, e, F, mapping, composition, id> seg(v);
    while (q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int l, r, b, c;
            std::cin >> l >> r >> b >> c;
            seg.apply(l, r, F(b, c));
        } else {
            int l, r;
            std::cin >> l >> r;
            std::cout << seg.prod(l, r).a.val() << std::endl;
        }
    }
}
Back to top page