test/yosupo/ds/segment_tree/point_set_range_composite_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/point_set_range_composite_large_array

Depends on

Code

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

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

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

using mint = modint998;
struct M {
    struct T {
        mint a = 1, b = 0;
        mint operator()(mint x) { return a * x + b; }
    };
    static T id() { return {}; }
    static T op(T l, T r) { return {r.a * l.a, r.a * l.b + r.b}; }
};

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

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

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

#line 2 "ds/dynsegtree.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/dynsegtree.hpp"

// clang-format off
template<class M, class I = int> struct DynSegTree {
    using T = typename M::T;
    DynSegTree() = default;
    DynSegTree(int _n) : n(_n), root(new node()) {}

    void set(I p, const T &x) const {
        assert(0 <= p && p < n);
        auto rec = [&](auto &self, ptr t, I l, I r) -> void {
            if (r - l == 1) return void(t->val = x);
            I m = (l + r) / 2;
            if (p < m) self(self, t->c(0), l, m);
            else self(self, t->c(1), m, r);
            t->val = M::op(val(t->l), val(t->r));
        };
        rec(rec, root, 0, n);
    }
    T operator[](I p) const {
        assert(0 <= p && p < n);
        auto rec = [&](auto &self, ptr t, I l, I r) -> T {
            if (!t) return M::id();
            if (r - l == 1) return t->val;
            I m = (l + r) / 2;
            return p < m ? self(self, t->l, l, m) : self(self, t->r, m, r);
        };
        return rec(rec, root, 0, n);
    }
    T get(I p) const { return (*this)[p]; }
    T operator()(I l, I r) const {
        assert(0 <= l && l <= r && r <= n);
        auto rec = [&](auto &self, ptr t, I tl, I tr) -> T {
            if (!t) return M::id();
            if (l <= tl && tr <= r) return t->val;
            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);
    }
    T prod(I l, I r) const { return (*this)(l, r); }
    T all_prod() const { return root->val; }

  private:
    struct node;
    using ptr = node *;
    struct node : st_alloc<node> {
        T val = M::id();
        ptr l = nullptr, r = nullptr;
        node() {}
        inline ptr c(bool z) {
            return !z ? l ? l : l = new node() : r ? r : r = new node();
        }
    };

    I n;
    ptr root;

    static inline T val(ptr t) { return t ? t->val : M::id(); }
};
// clang-format on
#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/point_set_range_composite_large_array.test.cpp"

using mint = modint998;
struct M {
    struct T {
        mint a = 1, b = 0;
        mint operator()(mint x) { return a * x + b; }
    };
    static T id() { return {}; }
    static T op(T l, T r) { return {r.a * l.a, r.a * l.b + r.b}; }
};

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

Test cases

Env	Name	Status	Elapsed	Memory
g++	dense_00	AC	172 ms	4 MB
g++	dense_01	AC	243 ms	4 MB
g++	dense_02	AC	373 ms	18 MB
g++	example_00	AC	5 ms	4 MB
g++	many_query_0_00	AC	578 ms	150 MB
g++	many_query_0_01	AC	600 ms	149 MB
g++	many_query_1_00	AC	263 ms	6 MB
g++	many_query_1_01	AC	262 ms	6 MB
g++	max_random_00	AC	526 ms	83 MB
g++	max_random_01	AC	520 ms	84 MB
g++	max_random_02	AC	511 ms	83 MB
g++	near_0_and_N_00	AC	370 ms	33 MB
g++	near_0_and_N_01	AC	370 ms	33 MB
g++	query_0_then_1_00	AC	593 ms	83 MB
g++	query_0_then_1_01	AC	578 ms	83 MB
g++	random_00	AC	403 ms	58 MB
g++	random_01	AC	428 ms	61 MB
g++	random_02	AC	370 ms	64 MB
g++	random_03	AC	25 ms	9 MB
g++	random_04	AC	92 ms	21 MB
g++	small_N_00	AC	117 ms	4 MB
g++	small_N_01	AC	118 ms	4 MB
g++	small_N_02	AC	122 ms	4 MB
g++	small_N_03	AC	124 ms	4 MB
g++	small_N_04	AC	124 ms	4 MB
clang++	dense_00	AC	201 ms	4 MB
clang++	dense_01	AC	254 ms	4 MB
clang++	dense_02	AC	392 ms	18 MB
clang++	example_00	AC	6 ms	4 MB
clang++	many_query_0_00	AC	593 ms	149 MB
clang++	many_query_0_01	AC	620 ms	149 MB
clang++	many_query_1_00	AC	255 ms	6 MB
clang++	many_query_1_01	AC	254 ms	6 MB
clang++	max_random_00	AC	522 ms	83 MB
clang++	max_random_01	AC	539 ms	83 MB
clang++	max_random_02	AC	568 ms	82 MB
clang++	near_0_and_N_00	AC	383 ms	33 MB
clang++	near_0_and_N_01	AC	372 ms	33 MB
clang++	query_0_then_1_00	AC	589 ms	83 MB
clang++	query_0_then_1_01	AC	552 ms	83 MB
clang++	random_00	AC	389 ms	58 MB
clang++	random_01	AC	375 ms	60 MB
clang++	random_02	AC	354 ms	65 MB
clang++	random_03	AC	24 ms	9 MB
clang++	random_04	AC	84 ms	21 MB
clang++	small_N_00	AC	112 ms	4 MB
clang++	small_N_01	AC	120 ms	4 MB
clang++	small_N_02	AC	118 ms	4 MB
clang++	small_N_03	AC	119 ms	4 MB
clang++	small_N_04	AC	122 ms	4 MB