test/segment_tree/sparse_segtree.test.cpp

• View this file on GitHub
• Last update: 2026-08-12 17:52:00+00:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite_large_array

Depends on

• monoids/affine_monoid.hpp
• segment_tree/sparse_segtree.hpp

Code

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

#include "segment_tree/sparse_segtree.hpp"
#include "monoids/affine_monoid.hpp"
#include <atcoder/modint>
#include <bits/stdc++.h>
using Z = atcoder::modint998244353;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    using S = AffineMonoid<Z>;
    sparse_segtree<int, S, S::op, S::e> seg(N);
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int p, c, d;
            std::cin >> p >> c >> d;
            seg.set(p, {c, d});
        } else {
            int l, r, x;
            std::cin >> l >> r >> x;
            auto [a, b] = seg.prod(l, r);
            auto ans = a * x + b;
            std::cout << ans.val() << "\n";
        }
    }
}

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

#line 1 "segment_tree/sparse_segtree.hpp"



#include <cassert>
#include <cstdint>
#include <vector>

// https://suisen-cp.github.io/cp-library-cpp/library/datastructure/segment_tree/sparse_segment_tree.hpp
template <typename IndexType, // type of index
          typename S,         // type of element
          auto op,            // S op(S a, S b)
          auto e,             // S e()
          auto init = [](IndexType, IndexType) { return e(); }
          // (l, r) -> init[l] * init[l+1] * ... * init[r-1]
          >
struct sparse_segtree {
    using index_type = IndexType;
    using value_type = S;

private:
    using pool_index_type = uint32_t;

    struct Node {
        pool_index_type ch[2]{0, 0};
        value_type dat;
        Node(const value_type &dat_) : dat(dat_) {}
    };

    static inline std::vector<Node> pool{Node{e()}};

    static pool_index_type new_node(const value_type &dat) {
        const pool_index_type res = static_cast<pool_index_type>(pool.size());
        return pool.emplace_back(dat), res;
    }

public:
    sparse_segtree() : sparse_segtree(0) {}
    explicit sparse_segtree(IndexType n_) : n(n_), root(new_node(init(0, n))) {}

    static void reserve(int siz) { pool.reserve(siz); }

    value_type get(index_type i) const {
        assert(0 <= i and i < n);
        pool_index_type cur = root;
        for (index_type l = 0, r = n; cur and r - l > 1;) {
            index_type m = l + (r - l) / 2;
            if (i < m)
                cur = pool[cur].ch[0], r = m;
            else
                cur = pool[cur].ch[1], l = m;
        }
        return get(cur, i, i + 1);
    }
    template <typename Fun> void apply_fun(index_type i, Fun &&fun) {
        assert(0 <= i and i < n);
        auto rec = [&](auto self, pool_index_type cur, index_type l, index_type r) -> void {
            if (r - l == 1) {
                pool[cur].dat = fun(get(cur, l, r));
                return;
            }
            const index_type m = l + (r - l) / 2;
            if (i < m)
                self(self, get_or_create_child(cur, 0, l, m), l, m);
            else
                self(self, get_or_create_child(cur, 1, m, r), m, r);
            pool[cur].dat = op(get(pool[cur].ch[0], l, m), get(pool[cur].ch[1], m, r));
        };
        rec(rec, root, 0, n);
    }
    void set(index_type i, const value_type &val) {
        apply_fun(i, [&val](const value_type &) { return val; });
    }

    value_type operator()(index_type l, index_type r) const {
        assert(0 <= l and l <= r and r <= n);
        return query(root, l, r, 0, n);
    }
    value_type prod(index_type l, index_type r) const { return (*this)(l, r); }
    value_type all_prod() const { return pool[root].dat; }

private:
    index_type n;
    pool_index_type root;

    value_type get(pool_index_type node, index_type tl, index_type tr) const {
        return node ? pool[node].dat : init(tl, tr);
    }

    pool_index_type get_or_create_child(pool_index_type node, int index, index_type tl,
                                        index_type tr) {
        if (pool[node].ch[index])
            return pool[node].ch[index];
        const pool_index_type ch = new_node(init(tl, tr));
        return pool[node].ch[index] = ch;
    }

    value_type query(pool_index_type node, index_type ql, index_type qr, index_type tl,
                     index_type tr) const {
        if (tr <= ql or qr <= tl)
            return e();
        if (not node)
            return init(std::max(ql, tl), std::min(qr, tr));
        if (ql <= tl and tr <= qr)
            return pool[node].dat;
        const index_type tm = tl + (tr - tl) / 2;
        return op(query(pool[node].ch[0], ql, qr, tl, tm), query(pool[node].ch[1], ql, qr, tm, tr));
    }
};


#line 1 "monoids/affine_monoid.hpp"



template <typename Z> struct AffineMonoid {
    static AffineMonoid op(AffineMonoid f, AffineMonoid g) {
        auto [a, b] = f;
        auto [c, d] = g;
        return {c * a, c * b + d};
    }
    static AffineMonoid e() { return {1, 0}; }
    Z a, b;
};


#line 5 "test/segment_tree/sparse_segtree.test.cpp"
#include <atcoder/modint>
#include <bits/stdc++.h>
using Z = atcoder::modint998244353;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    using S = AffineMonoid<Z>;
    sparse_segtree<int, S, S::op, S::e> seg(N);
    while (Q--) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int p, c, d;
            std::cin >> p >> c >> d;
            seg.set(p, {c, d});
        } else {
            int l, r, x;
            std::cin >> l >> r >> x;
            auto [a, b] = seg.prod(l, r);
            auto ans = a * x + b;
            std::cout << ans.val() << "\n";
        }
    }
}

Back to top page