cp-library-cpp

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

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/datastructure/segment_tree/dual_segment_tree/range_affine_point_get.test.cpp

Depends on

Code

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

#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

#include "library/datastructure/segment_tree/dual_segment_tree.hpp"

mint mapping(std::pair<mint, mint> f, mint x) {
    return f.first * x + f.second;
}
std::pair<mint, mint> composition(std::pair<mint, mint> f, std::pair<mint, mint> g) {
    return { f.first * g.first, f.first * g.second + f.second };
}
std::pair<mint, mint> id() {
    return { 1, 0 };
}
using Segtree = suisen::DualSegmentTree<mint, std::pair<mint, mint>, mapping, composition, id>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::vector<mint> a(n);
    for (auto &e : a) {
        int v;
        std::cin >> v;
        e = v;
    }

    Segtree seg(a);
    while (q --> 0) {
        int query_type;
        std::cin >> query_type;
        if (query_type == 0) {
            int l, r, b, c;
            std::cin >> l >> r >> b >> c;
            seg.apply(l, r, { b, c });
        } else {
            int x;
            std::cin >> x;
            std::cout << seg.get(x).val() << '\n';
        }
    }

    return 0;
}
#line 1 "test/src/datastructure/segment_tree/dual_segment_tree/range_affine_point_get.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_point_get"

#include <iostream>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

#line 1 "library/datastructure/segment_tree/dual_segment_tree.hpp"



#line 1 "library/datastructure/segment_tree/commutative_dual_segment_tree.hpp"



#include <cassert>
#include <vector>

namespace suisen {
    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    struct CommutativeDualSegmentTree {
        CommutativeDualSegmentTree() = default;
        CommutativeDualSegmentTree(std::vector<T>&& a) : n(a.size()), m(ceil_pow2(a.size())), data(std::move(a)), lazy(m, id()) {}
        CommutativeDualSegmentTree(const std::vector<T>& a) : CommutativeDualSegmentTree(std::vector<T>(a)) {}
        CommutativeDualSegmentTree(int n, const T& fill_value) : CommutativeDualSegmentTree(std::vector<T>(n, fill_value)) {}

        T operator[](int i) const {
            assert(0 <= i and i < n);
            T res = data[i];
            for (i = (i + m) >> 1; i; i >>= 1) res = mapping(lazy[i], res);
            return res;
        }
        T get(int i) const {
            return (*this)[i];
        }
        void apply(int l, int r, const F& f) {
            assert(0 <= l and r <= n);
            for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) apply(l++, f);
                if (r & 1) apply(--r, f);
            }
        }
    protected:
        int n, m;
        std::vector<T> data;
        std::vector<F> lazy;

        void apply(int k, const F& f) {
            if (k < m) {
                lazy[k] = composition(f, lazy[k]);
            } else if (k - m < n) {
                data[k - m] = mapping(f, data[k - m]);
            }
        }
    private:
        static int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }
    };
} // namespace suisen


#line 5 "library/datastructure/segment_tree/dual_segment_tree.hpp"

namespace suisen {
    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    struct DualSegmentTree : public CommutativeDualSegmentTree<T, F, mapping, composition, id> {
        using base_type = CommutativeDualSegmentTree<T, F, mapping, composition, id>;
        using base_type::base_type;
        void apply(int l, int r, const F& f) {
            push(l, r);
            base_type::apply(l, r, f);
        }
    private:
        void push(int k) {
            base_type::apply(2 * k, this->lazy[k]), base_type::apply(2 * k + 1, this->lazy[k]);
            this->lazy[k] = id();
        }
        void push(int l, int r) {
            const int log = __builtin_ctz(this->m);

            l += this->m, r += this->m;

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

    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    DualSegmentTree(int, T)->DualSegmentTree<T, F, mapping, composition, id>;

    template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
    DualSegmentTree(std::vector<T>)->DualSegmentTree<T, F, mapping, composition, id>;
} // namespace suisen



#line 9 "test/src/datastructure/segment_tree/dual_segment_tree/range_affine_point_get.test.cpp"

mint mapping(std::pair<mint, mint> f, mint x) {
    return f.first * x + f.second;
}
std::pair<mint, mint> composition(std::pair<mint, mint> f, std::pair<mint, mint> g) {
    return { f.first * g.first, f.first * g.second + f.second };
}
std::pair<mint, mint> id() {
    return { 1, 0 };
}
using Segtree = suisen::DualSegmentTree<mint, std::pair<mint, mint>, mapping, composition, id>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    std::vector<mint> a(n);
    for (auto &e : a) {
        int v;
        std::cin >> v;
        e = v;
    }

    Segtree seg(a);
    while (q --> 0) {
        int query_type;
        std::cin >> query_type;
        if (query_type == 0) {
            int l, r, b, c;
            std::cin >> l >> r >> b >> c;
            seg.apply(l, r, { b, c });
        } else {
            int x;
            std::cin >> x;
            std::cout << seg.get(x).val() << '\n';
        }
    }

    return 0;
}
Back to top page