test/yosupo/ds/segment_tree/range_affine_range_sum_large_array.test.cpp

View this file on GitHub
Last update: 2025-09-20 17:47:50+07:00
Problem: https://judge.yosupo.jp/problem/range_affine_range_sum_large_array

Depends on

Code

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

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

#include "ds/dynlazysegtree.hpp"
#include "math/modint.hpp"

using mint = modint998;
struct M {
    using T = mint;
    using F = array<mint, 2>;
    static T id() { return 0; }
    static F fid() { return {1, 0}; }
    static T op(T l, T r) { return l + r; }
    static F comp(const F &l, const F &r) {
        return {l[0] * r[0], l[0] * r[1] + l[1]};
    }
    static T map(const F &f, T x, int l, int r) {
        x = x * f[0] + (r - l) * f[1];
        return x;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    DynLazySegTree<M> st(n);
    while (q--) {
        int t, l, r, b, c;
        cin >> t >> l >> r;
        if (t == 0) {
            cin >> b >> c;
            st.apply(l, r, {b, c});
        } else {
            cout << st(l, r) << "\n";
        }
    }
}

#line 1 "test/yosupo/ds/segment_tree/range_affine_range_sum_large_array.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum_large_array"

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

#line 2 "ds/dynlazysegtree.hpp"

#line 2 "other/st_alloc.hpp"

template<class T> struct st_alloc {
    static inline stack<T> pool;
    void *operator new(size_t) { return pool.emplace(), &pool.top(); }
    void operator delete(void *) {}
};
#line 4 "ds/dynlazysegtree.hpp"

template<class M, class I = int> struct DynLazySegTree {
    using T = typename M::T;
    using F = typename M::F;

    struct node;
    using ptr = node *;
    struct node : st_alloc<node> {
        ptr l = 0, r = 0;
        T x = M::id();
        F lz = M::fid();

        node() {}

        ptr ch(bool z) {
            auto &c = !z ? l : r;
            return c = c ?: new node();
        }
    };

    I n;
    ptr root = 0;

    DynLazySegTree() {}
    DynLazySegTree(I _n) : n(_n), root(new node()) {}

    T operator()(I l, I r) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (r <= tl || tr <= l) return M::id();
            if (l <= tl && tr <= r) return t->x;
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (r <= tm) return self(self, t->l, tl, tm);
            if (tm <= l) return self(self, t->r, tm, tr);
            return M::op(self(self, t->l, tl, tm), self(self, t->r, tm, tr));
        };
        return rec(rec, root, 0, n);
    }
    void apply(I l, I r, const F &f) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (r <= tl || tr <= l) return;
            if (l <= tl && tr <= r) return all_apply(t, f, tl, tr);
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (r <= tm) {
                self(self, t->l, tl, tm);
            } else if (tm <= l) {
                self(self, t->r, tm, tr);
            } else {
                self(self, t->l, tl, tm), self(self, t->r, tm, tr);
            }
            update(t);
        };
        rec(rec, root, 0, n);
    }
    template<class G> I max_right(I l, G &&g) const {
        assert(0 <= l && l <= n);
        assert(g(M::id()));
        if (l == n) return n;
        I r = l;
        T sm = M::id();
        auto rec = [&](auto &self, ptr t, I tl, I tr) {
            if (tr - tl == 1) return r = g(M::op(sm, t->x)) ? tr : tl, t->x;
            if (l <= tl && g(M::op(sm, t->x))) return r = tr, t->x;
            push(t, tl, tr);
            I tm = (tl + tr) / 2;
            if (tm <= l) return self(self, t->r, tm, tr);
            auto lx = self(self, t->l, tl, tm);
            if (!g(M::op(sm, lx))) return lx;
            sm = M::op(sm, lx);
            return self(self, t->r, tm, tr);
        };
        rec(rec, root, 0, n);
        return r;
    }

  private:
    static void update(ptr t) { t->x = M::op(t->l->x, t->r->x); }
    static void all_apply(ptr t, const F &f, I tl, I tr) {
        t->x = M::map(f, t->x, tl, tr);
        t->lz = M::comp(f, t->lz);
    }
    static void push(ptr t, I tl, I tr) {
        I tm = (tl + tr) / 2;
        all_apply(t->ch(0), t->lz, tl, tm);
        all_apply(t->ch(1), t->lz, tm, tr);
        t->lz = M::fid();
    }
};
#line 2 "math/modint.hpp"

// clang-format off
template<uint32_t m> struct modint {
    static_assert(m >= 1, "Modulus must be in the range [1;2^31)");

    using mint = modint;
    static constexpr bool is_simple = true;

    static constexpr uint32_t mod() noexcept { return m; }
    constexpr modint() noexcept = default;
    constexpr modint(int64_t v) noexcept : _v(uint32_t((v %= m) < 0 ? v + m : v)) {}
    constexpr static mint raw(uint32_t v) noexcept { mint x; return x._v = v, x; }
    template<class T> constexpr explicit operator T() const noexcept { return _v; }

    constexpr mint &operator++() noexcept { return _v = ++_v == mod() ? 0 : _v, *this; }
    constexpr mint &operator--() noexcept { --(_v ? _v : _v = mod()); return *this; }
    constexpr mint operator++(int) noexcept { return exchange(*this, ++mint(*this)); }
    constexpr mint operator--(int) noexcept { return exchange(*this, --mint(*this)); }

    constexpr mint &operator+=(mint rhs) noexcept {
        return _v = int(_v += rhs._v - mod()) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator-=(mint rhs) noexcept {
        return _v = int(_v -= rhs._v) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator*=(mint rhs) noexcept {
        return _v = uint64_t(_v) * rhs._v % mod(), *this;
    }
    constexpr mint &operator/=(mint rhs) noexcept {
        return *this = *this * rhs.inv();
    }

    constexpr friend mint operator+(mint l, mint r) noexcept { return l += r; }
    constexpr friend mint operator-(mint l, mint r) noexcept { return l -= r; }
    constexpr friend mint operator*(mint l, mint r) noexcept { return l *= r; }
    constexpr friend mint operator/(mint l, mint r) noexcept { return l /= r; }

    constexpr mint operator+() const noexcept { return *this; }
    constexpr mint operator-() const noexcept { return raw(_v ? mod() - _v : 0); }

    constexpr friend bool operator==(mint l, mint r) noexcept { return l._v == r._v; }
    constexpr friend bool operator!=(mint l, mint r) noexcept { return l._v != r._v; }
    constexpr friend bool operator<(mint l, mint r) noexcept { return l._v < r._v; }

    constexpr mint pow(uint64_t n) const noexcept {
        mint b = *this, res = 1;
        while (n) n & 1 ? res *= b : 0, b *= b, n >>= 1;
        return res;
    }

    constexpr mint inv() const noexcept {
        int a = _v, b = mod(), x = 1, y = 0;
        while (b) {
            x = exchange(y, x - a / b * y);
            a = exchange(b, a % b);
        }
        assert(a == 1);
        return x;
    }

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

  private:
    uint32_t _v = 0;
};
using modint107 = modint<1'000'000'007>;
using modint998 = modint<998'244'353>;
// clang-format on
#line 8 "test/yosupo/ds/segment_tree/range_affine_range_sum_large_array.test.cpp"

using mint = modint998;
struct M {
    using T = mint;
    using F = array<mint, 2>;
    static T id() { return 0; }
    static F fid() { return {1, 0}; }
    static T op(T l, T r) { return l + r; }
    static F comp(const F &l, const F &r) {
        return {l[0] * r[0], l[0] * r[1] + l[1]};
    }
    static T map(const F &f, T x, int l, int r) {
        x = x * f[0] + (r - l) * f[1];
        return x;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    DynLazySegTree<M> st(n);
    while (q--) {
        int t, l, r, b, c;
        cin >> t >> l >> r;
        if (t == 0) {
            cin >> b >> c;
            st.apply(l, r, {b, c});
        } else {
            cout << st(l, r) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	dense_00	AC	75 ms	4 MB
g++	dense_01	AC	99 ms	4 MB
g++	dense_02	AC	155 ms	23 MB
g++	example_00	AC	5 ms	4 MB
g++	many_query_0_00	AC	312 ms	155 MB
g++	many_query_0_01	AC	315 ms	153 MB
g++	many_query_1_00	AC	289 ms	153 MB
g++	many_query_1_01	AC	285 ms	153 MB
g++	max_random_00	AC	300 ms	155 MB
g++	max_random_01	AC	299 ms	153 MB
g++	max_random_02	AC	304 ms	155 MB
g++	near_0_and_N_00	AC	197 ms	60 MB
g++	near_0_and_N_01	AC	199 ms	60 MB
g++	query_0_then_1_00	AC	296 ms	153 MB
g++	query_0_then_1_01	AC	299 ms	153 MB
g++	random_00	AC	52 ms	30 MB
g++	random_01	AC	58 ms	34 MB
g++	random_02	AC	183 ms	98 MB
g++	random_03	AC	79 ms	47 MB
g++	random_04	AC	294 ms	149 MB
g++	small_N_00	AC	25 ms	4 MB
g++	small_N_01	AC	27 ms	4 MB
g++	small_N_02	AC	28 ms	4 MB
g++	small_N_03	AC	28 ms	4 MB
g++	small_N_04	AC	29 ms	4 MB
g++	small_Q_00	AC	4 ms	4 MB
g++	small_Q_01	AC	4 ms	4 MB
g++	small_Q_02	AC	4 ms	4 MB
g++	small_Q_03	AC	4 ms	4 MB
g++	small_Q_04	AC	4 ms	4 MB
g++	small_Q_05	AC	4 ms	4 MB
clang++	dense_00	AC	81 ms	4 MB
clang++	dense_01	AC	106 ms	4 MB
clang++	dense_02	AC	159 ms	23 MB
clang++	example_00	AC	5 ms	4 MB
clang++	many_query_0_00	AC	331 ms	155 MB
clang++	many_query_0_01	AC	321 ms	155 MB
clang++	many_query_1_00	AC	288 ms	155 MB
clang++	many_query_1_01	AC	285 ms	153 MB
clang++	max_random_00	AC	304 ms	153 MB
clang++	max_random_01	AC	303 ms	155 MB
clang++	max_random_02	AC	314 ms	155 MB
clang++	near_0_and_N_00	AC	205 ms	60 MB
clang++	near_0_and_N_01	AC	200 ms	60 MB
clang++	query_0_then_1_00	AC	301 ms	155 MB
clang++	query_0_then_1_01	AC	298 ms	155 MB
clang++	random_00	AC	53 ms	30 MB
clang++	random_01	AC	59 ms	34 MB
clang++	random_02	AC	186 ms	98 MB
clang++	random_03	AC	80 ms	46 MB
clang++	random_04	AC	296 ms	147 MB
clang++	small_N_00	AC	27 ms	4 MB
clang++	small_N_01	AC	26 ms	4 MB
clang++	small_N_02	AC	28 ms	4 MB
clang++	small_N_03	AC	29 ms	4 MB
clang++	small_N_04	AC	30 ms	4 MB
clang++	small_Q_00	AC	4 ms	3 MB
clang++	small_Q_01	AC	4 ms	4 MB
clang++	small_Q_02	AC	4 ms	4 MB
clang++	small_Q_03	AC	4 ms	4 MB
clang++	small_Q_04	AC	4 ms	4 MB
clang++	small_Q_05	AC	4 ms	4 MB