This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#define PROBLEM \ "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum" #include <iostream> #include "../../data_structure/ImplicitTreap.hpp" #include "../../modint/modint.hpp" #include "../../template/int_alias.hpp" using mint = ebi::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}; } using ebi::i64; int main() { ebi::ImplicitTreap<S, op, e, F, mapping, composition, id> treap; int n, q; std::cin >> n >> q; for (int i = 0; i < n; i++) { i64 a; std::cin >> a; treap.insert(i, {a, 1}); } while (q--) { int t; std::cin >> t; if (t == 0) { int i; i64 x; std::cin >> i >> x; treap.insert(i, {x, 1}); } else if (t == 1) { int i; std::cin >> i; treap.erase(i); } else if (t == 2) { int l, r; std::cin >> l >> r; treap.reverse(l, r); } else if (t == 3) { int l, r, b, c; std::cin >> l >> r >> b >> c; treap.apply(l, r, F(b, c)); } else if (t == 4) { int l, r; std::cin >> l >> r; std::cout << treap.prod(l, r).a.value() << std::endl; } } }
#line 1 "test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp" #define PROBLEM \ "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum" #include <iostream> #line 2 "data_structure/ImplicitTreap.hpp" /* reference: https://www.slideshare.net/iwiwi/2-12188757 実装方法やTreapのアイデアなど. https://xuzijian629.hatenablog.com/entry/2018/12/08/000452 Treapをリストのように扱う方法や実装法, Monoidの載せ方など. */ #include <random> namespace ebi { template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct ImplicitTreap { private: struct Node { S val, acc; F lazy; int pri, cnt; bool rev; Node *lch, *rch; Node(S val, int pri) : val(val), acc(e()), lazy(id()), pri(pri), cnt(0), rev(false), lch(nullptr), rch(nullptr) {} }; using node_ptr = Node *; node_ptr root; std::random_device rnd; std::mt19937 mt; std::uniform_int_distribution<> pri_rnd; int cnt(node_ptr t) { return t ? t->cnt : 0; } void update_cnt(node_ptr t) { if (t) { t->cnt = 1 + cnt(t->lch) + cnt(t->rch); } } S acc(node_ptr t) { return t ? t->acc : e(); } void update_acc(node_ptr t) { if (t) { t->acc = op(acc(t->lch), t->val); t->acc = op(t->acc, acc(t->rch)); } } void eval(node_ptr t) { if (t) { if (t->lch) { t->lch->lazy = composition(t->lazy, t->lch->lazy); t->lch->acc = mapping(t->lazy, t->lch->acc); } if (t->rch) { t->rch->lazy = composition(t->lazy, t->rch->lazy); t->rch->acc = mapping(t->lazy, t->rch->acc); } t->val = mapping(t->lazy, t->val); t->lazy = id(); } } void pushdown(node_ptr t) { if (t && t->rev) { t->rev = false; std::swap(t->lch, t->rch); if (t->lch) t->lch->rev ^= 1; if (t->rch) t->rch->rev ^= 1; } eval(t); update(t); } void update(node_ptr t) { update_cnt(t); update_acc(t); } node_ptr merge(node_ptr l, node_ptr r) { pushdown(l); pushdown(r); if (!l || !r) { return !l ? r : l; } if (l->pri > r->pri) { l->rch = merge(l->rch, r); update(l); return l; } else { r->lch = merge(l, r->lch); update(r); return r; } } std::pair<node_ptr, node_ptr> split(node_ptr t, int key) { if (!t) return std::pair<node_ptr, node_ptr>(nullptr, nullptr); pushdown(t); if (key < cnt(t->lch) + 1) { auto [l, r] = split(t->lch, key); t->lch = r; update(t); return std::pair<node_ptr, node_ptr>(l, t); } else { auto [l, r] = split(t->rch, key - cnt(t->lch) - 1); t->rch = l; update(t); return std::pair<node_ptr, node_ptr>(t, r); } } public: ImplicitTreap() : root(nullptr) { mt = std::mt19937(rnd()); pri_rnd = std::uniform_int_distribution<>(0, 1e9); } void insert(int k, S x) { auto [l, r] = split(root, k); auto t = merge(l, new Node(x, pri_rnd(mt))); root = merge(t, r); } void erase(int k) { auto [l, r] = split(root, k + 1); auto [nl, nr] = split(l, k); root = merge(nl, r); } void reverse(int l, int r) { auto [t1, t2] = split(root, l); auto [t3, t4] = split(t2, r - l); t3->rev ^= 1; t1 = merge(t1, t3); root = merge(t1, t4); } void apply(int l, int r, F x) { auto [t1, t2] = split(root, l); auto [t3, t4] = split(t2, r - l); t3->lazy = composition(x, t3->lazy); t3->acc = mapping(x, t3->acc); t1 = merge(t1, t3); root = merge(t1, t4); } S prod(int l, int r) { auto [t1, t2] = split(root, l); auto [t3, t4] = split(t2, r - l); S ret = t3->acc; t1 = merge(t1, t3); root = merge(t1, t4); return ret; } }; } // namespace ebi #line 2 "modint/modint.hpp" #include <cassert> #line 5 "modint/modint.hpp" #line 2 "modint/base.hpp" #include <concepts> #line 5 "modint/base.hpp" #include <utility> namespace ebi { template <class T> concept Modint = requires(T a, T b) { a + b; a - b; a * b; a / b; a.inv(); a.val(); a.pow(std::declval<long long>()); T::mod(); }; template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) { long long x; os >> x; a = x; return os; } template <Modint mint> std::ostream &operator<<(std::ostream &os, const mint &a) { return os << a.val(); } } // namespace ebi #line 7 "modint/modint.hpp" namespace ebi { template <int m> struct static_modint { private: using modint = static_modint; public: static constexpr int mod() { return m; } static constexpr modint raw(int v) { modint x; x._v = v; return x; } constexpr static_modint() : _v(0) {} constexpr static_modint(long long v) { v %= (long long)umod(); if (v < 0) v += (long long)umod(); _v = (unsigned int)v; } constexpr unsigned int val() const { return _v; } constexpr unsigned int value() const { return val(); } constexpr modint &operator++() { _v++; if (_v == umod()) _v = 0; return *this; } constexpr modint &operator--() { if (_v == 0) _v = umod(); _v--; return *this; } constexpr modint operator++(int) { modint res = *this; ++*this; return res; } constexpr modint operator--(int) { modint res = *this; --*this; return res; } constexpr modint &operator+=(const modint &rhs) { _v += rhs._v; if (_v >= umod()) _v -= umod(); return *this; } constexpr modint &operator-=(const modint &rhs) { _v -= rhs._v; if (_v >= umod()) _v += umod(); return *this; } constexpr modint &operator*=(const modint &rhs) { unsigned long long x = _v; x *= rhs._v; _v = (unsigned int)(x % (unsigned long long)umod()); return *this; } constexpr modint &operator/=(const modint &rhs) { return *this = *this * rhs.inv(); } constexpr modint operator+() const { return *this; } constexpr modint operator-() const { return modint() - *this; } constexpr modint pow(long long n) const { assert(0 <= n); modint x = *this, res = 1; while (n) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } constexpr modint inv() const { assert(_v); return pow(umod() - 2); } friend modint operator+(const modint &lhs, const modint &rhs) { return modint(lhs) += rhs; } friend modint operator-(const modint &lhs, const modint &rhs) { return modint(lhs) -= rhs; } friend modint operator*(const modint &lhs, const modint &rhs) { return modint(lhs) *= rhs; } friend modint operator/(const modint &lhs, const modint &rhs) { return modint(lhs) /= rhs; } friend bool operator==(const modint &lhs, const modint &rhs) { return lhs.val() == rhs.val(); } friend bool operator!=(const modint &lhs, const modint &rhs) { return !(lhs == rhs); } private: unsigned int _v = 0; static constexpr unsigned int umod() { return m; } }; using modint998244353 = static_modint<998244353>; using modint1000000007 = static_modint<1000000007>; } // namespace ebi #line 2 "template/int_alias.hpp" #include <cstdint> namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 9 "test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp" using mint = ebi::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}; } using ebi::i64; int main() { ebi::ImplicitTreap<S, op, e, F, mapping, composition, id> treap; int n, q; std::cin >> n >> q; for (int i = 0; i < n; i++) { i64 a; std::cin >> a; treap.insert(i, {a, 1}); } while (q--) { int t; std::cin >> t; if (t == 0) { int i; i64 x; std::cin >> i >> x; treap.insert(i, {x, 1}); } else if (t == 1) { int i; std::cin >> i; treap.erase(i); } else if (t == 2) { int l, r; std::cin >> l >> r; treap.reverse(l, r); } else if (t == 3) { int l, r, b, c; std::cin >> l >> r >> b >> c; treap.apply(l, r, F(b, c)); } else if (t == 4) { int l, r; std::cin >> l >> r; std::cout << treap.prod(l, r).a.value() << std::endl; } } }