This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/deque_operate_all_composite" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #include "library/algebra/monoid/affine.hpp" #include "library/datastructure/deque_aggregation.hpp" using suisen::Affine; using suisen::DequeAggregation; Affine<mint> op(Affine<mint> f, Affine<mint> g) { return g.compose(f); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); DequeAggregation<Affine<mint>, op, Affine<mint>::id> dq; int q; std::cin >> q; for (int i = 0; i < q; ++i) { int query_type; std::cin >> query_type; if (query_type == 0) { int a, b; std::cin >> a >> b; dq.push_front({ a, b }); } else if (query_type == 1) { int a, b; std::cin >> a >> b; dq.push_back({ a, b }); } else if (query_type == 2) { dq.pop_front(); } else if (query_type == 3) { dq.pop_back(); } else { int x; std::cin >> x; std::cout << dq.prod().affine(x).val() << '\n'; } } return 0; }
#line 1 "test/src/datastructure/deque_aggregation/deque_operate_all_composite.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/deque_operate_all_composite" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #line 1 "library/algebra/monoid/affine.hpp" #line 5 "library/algebra/monoid/affine.hpp" #include <utility> namespace suisen { template <typename T> struct Affine { T a, b; Affine(const T &a = 1, const T &b = 0) : a(a), b(b) {} static Affine<T> id() { return Affine<T>{}; } static Affine<T> compose(const Affine<T>& f, const Affine<T>& g) { return f.compose(g); } Affine<T> compose(const Affine<T>& g) const { return { a * g.a, affine(g.b) }; } template <typename U = T> U affine(const T &x) const { return U(a) * x + b; } T operator()(const T &x) const { return affine<T>(x); } Affine<T> operator+() const { return *this; } Affine<T> operator-() const { return { -a, -b }; } Affine<T>& operator++() { ++b; return *this; } Affine<T>& operator--() { --b; return *this; } Affine<T> operator++(int) { Affine<T> f(*this); ++(*this); return f; } Affine<T> operator--(int) { Affine<T> f(*this); --(*this); return f; } Affine<T>& operator+=(const T& c) { b += c; return *this; } Affine<T>& operator-=(const T& c) { b -= c; return *this; } friend Affine<T> operator+(Affine<T> f, const T &c) { f += c; return f; } friend Affine<T> operator-(Affine<T> f, const T &c) { f -= c; return f; } Affine<T>& operator+=(const Affine<T> &g) { a += g.a, b += g.b; return *this; } Affine<T>& operator-=(const Affine<T> &g) { a -= g.a, b -= g.b; return *this; } friend Affine<T> operator+(Affine<T> f, const Affine<T> &g) { f += g; return f; } friend Affine<T> operator-(Affine<T> f, const Affine<T> &g) { f -= g; return f; } friend bool operator==(const Affine<T> &f, const Affine<T> &g) { return f.a == g.a and f.b == g.b; } friend bool operator!=(const Affine<T> &f, const Affine<T> &g) { return not (f == g); } friend bool operator< (const Affine<T> &f, const Affine<T> &g) { return f.a < g.a or (f.a == g.a and f.b < g.b); } friend bool operator<=(const Affine<T> &f, const Affine<T> &g) { return not (g < f); } friend bool operator> (const Affine<T> &f, const Affine<T> &g) { return g < f; } friend bool operator>=(const Affine<T> &f, const Affine<T> &g) { return not (f < g); } template <typename U = T, typename V = T> operator std::pair<U, V>() { return std::pair<U, V>{ a, b }; } template <typename U = T, typename V = T> operator std::tuple<U, V>() { return std::tuple<U, V>{ a, b }; } friend std::istream& operator<<(std::istream& in, Affine<T> &f) { return in >> f.a >> f.b; } friend std::ostream& operator>>(std::ostream& out, const Affine<T> &f) { return out << f.a << ' ' << f.b; } }; } // namespace suisen #line 1 "library/datastructure/deque_aggregation.hpp" #include <cassert> #include <vector> /** * [Idea] reference : https://motsu-xe.hatenablog.com/entry/2021/05/13/224016 * * SWAG + simulate a deque with 2 stacks * * [Operations] reference : https://www.slideshare.net/catupper/amortize-analysis-of-deque-with-2-stack * * `l`, `r` is a stack of { value, sum } * * accumulate * <---------- ------> fold values from inside * ( l ][ r ) * * pop_front: * 1. `l` is not empty * ( l ][ r ) -> ( l ][ r ) # pop from `l`. O(1) * 2. `l` is empty * (][ r ) -> ( l ][ r ) # split `r` at its middle point. amortized O(1) * ( l ][ r ) -> ( l ][ r ) # pop from `l`. O(1) * * pop_back: * 1. `r` is not empty * ( l ][ r ) -> ( l ][ r ) # pop from `r`. O(1) * 2. `r` is empty * ( l ][) -> ( l ][ r ) # split `l` at its middle point. amortized O(1) * ( l ][ r ) -> ( l ][ r ) # pop from `r`. O(1) * * push_front: * ( l ][ r ) -> ( l ][ r ) # push to `l`. O(1) * * push_back: * ( l ][ r ) -> ( l ][ r ) # push to `r`. O(1) */ namespace suisen { template <typename T, T(*op)(T, T), T(*e)()> struct DequeAggregation { struct DequeAggregationIterator { using difference_type = int; using value_type = T; using pointer = value_type*; using reference = value_type&; using iterator_category = std::random_access_iterator_tag; using fi_iterator_type = typename std::vector<std::pair<value_type, value_type>>::const_reverse_iterator; using se_iterator_type = typename std::vector<std::pair<value_type, value_type>>::const_iterator; fi_iterator_type it_l; fi_iterator_type it_l_end; se_iterator_type it_r_begin; se_iterator_type it_r; DequeAggregationIterator& operator++() { if (it_l == it_l_end) ++it_r; else ++it_l; return *this; } DequeAggregationIterator operator++(int) { DequeAggregationIterator ret = *this; ++(*this); return ret; } DequeAggregationIterator& operator--() { if (it_r == it_r_begin) --it_l; else --it_r; return *this; } DequeAggregationIterator operator--(int) { DequeAggregationIterator ret = *this; --(*this); return ret; } DequeAggregationIterator& operator+=(difference_type dif) { if (dif < 0) return *this -= -dif; if (int d = it_l_end - it_l; d < dif) it_l = it_l_end, it_r += dif - d; else it_l += dif; return *this; } friend DequeAggregationIterator operator+(DequeAggregationIterator it, difference_type dif) { it += dif; return it; } friend DequeAggregationIterator operator+(difference_type dif, DequeAggregationIterator it) { it += dif; return it; } DequeAggregationIterator& operator-=(difference_type dif) { if (dif < 0) return *this += -dif; if (int d = it_r - it_r_begin; d < dif) it_r = it_r_begin, it_l -= dif - d; else it_r -= dif; return *this; } friend DequeAggregationIterator operator-(DequeAggregationIterator it, difference_type dif) { it -= dif; return it; } difference_type operator-(const DequeAggregationIterator &rhs) const { difference_type d1 = it_l == it_l_end ? it_r - it_r_begin : it_l - it_l_end; difference_type d2 = rhs.it_l == rhs.it_l_end ? rhs.it_r - rhs.it_r_begin : rhs.it_l - rhs.it_l_end; return d1 - d2; } const value_type& operator[](difference_type i) const { return *((*this) + i); } const value_type& operator*() const { return it_l == it_l_end ? it_r->first : it_l->first; } bool operator!=(const DequeAggregationIterator &rhs) const { return it_l != rhs.it_l or it_r != rhs.it_r; } bool operator==(const DequeAggregationIterator &rhs) const { return not (*this != rhs); } bool operator< (const DequeAggregationIterator &rhs) const { return (*this) - rhs < 0; } bool operator<=(const DequeAggregationIterator &rhs) const { return (*this) - rhs <= 0; } bool operator> (const DequeAggregationIterator &rhs) const { return (*this) - rhs > 0; } bool operator>=(const DequeAggregationIterator &rhs) const { return (*this) - rhs >= 0; } }; using iterator = DequeAggregationIterator; using difference_type = typename iterator::difference_type; using value_type = typename iterator::value_type; using pointer = typename iterator::pointer; using reference = typename iterator::reference; DequeAggregation() = default; template <typename InputIterator, std::enable_if_t<std::is_constructible_v<value_type, typename InputIterator::value_type>, std::nullptr_t> = nullptr> DequeAggregation(InputIterator first, InputIterator last) { for (; first != last; ++first) push_back(*first); } template <typename Container, std::enable_if_t<std::is_constructible_v<value_type, typename Container::value_type>, std::nullptr_t> = nullptr> DequeAggregation(const Container &c) : DequeAggregation(std::begin(c), std::end(c)) {} value_type prod() const { return op(prod(_st_l), prod(_st_r)); } void push_back(const value_type &val) { _st_r.emplace_back(val, op(prod(_st_r), val)); } void push_front(const value_type &val) { _st_l.emplace_back(val, op(val, prod(_st_l))); } void pop_back() { if (_st_r.size()) return _st_r.pop_back(); const int siz = _st_l.size(); const int l = siz >> 1, r = siz - l; assert(r); // <=> siz > 0 for (int i = r - 1; i > 0; --i) push_back(std::move(_st_l[i].first)); _st_l.erase(_st_l.begin(), _st_l.begin() + r); if (l == 0) return; _st_l[0].second = _st_l[0].first; for (int i = 1; i < l; ++i) _st_l[i].second = op(_st_l[i].first, _st_l[i - 1].second); } void pop_front() { if (_st_l.size()) return _st_l.pop_back(); const int siz = _st_r.size(); const int r = siz >> 1, l = siz - r; assert(l); // <=> siz > 0 for (int i = l - 1; i > 0; --i) push_front(std::move(_st_r[i].first)); _st_r.erase(_st_r.begin(), _st_r.begin() + l); if (r == 0) return; _st_r[0].second = _st_r[0].first; for (int i = 1; i < r; ++i) _st_r[i].second = op(_st_r[i - 1].second, _st_r[i].first); } const value_type& front() const { return _st_l.size() ? _st_l.back().first : _st_r.front().first; } const value_type& back() const { return _st_r.size() ? _st_r.back().first : _st_l.front().first; } const value_type& operator[](int i) const { const int k = i - _st_l.size(); return k < 0 ? _st_l[~k].first : _st_r[k].first; } int size() const { return _st_l.size() + _st_r.size(); } void clear() { _st_l.clear(), _st_r.clear(); } void shrink_to_fit() { _st_l.shrink_to_fit(), _st_r.shrink_to_fit(); } iterator begin() const { return iterator { _st_l.rbegin(), _st_l.rend(), _st_r.begin(), _st_r.begin() }; } iterator end() const { return iterator { _st_l.rend(), _st_l.rend(), _st_r.begin(), _st_r.end() }; } iterator cbegin() const { return begin(); } iterator cend() const { return end(); } private: std::vector<std::pair<value_type, value_type>> _st_l, _st_r; value_type prod(const std::vector<std::pair<value_type, value_type>> &st) const { return st.empty() ? e() : st.back().second; } }; } // namespace suisen #line 11 "test/src/datastructure/deque_aggregation/deque_operate_all_composite.test.cpp" using suisen::Affine; using suisen::DequeAggregation; Affine<mint> op(Affine<mint> f, Affine<mint> g) { return g.compose(f); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); DequeAggregation<Affine<mint>, op, Affine<mint>::id> dq; int q; std::cin >> q; for (int i = 0; i < q; ++i) { int query_type; std::cin >> query_type; if (query_type == 0) { int a, b; std::cin >> a >> b; dq.push_front({ a, b }); } else if (query_type == 1) { int a, b; std::cin >> a >> b; dq.push_back({ a, b }); } else if (query_type == 2) { dq.pop_front(); } else if (query_type == 3) { dq.pop_back(); } else { int x; std::cin >> x; std::cout << dq.prod().affine(x).val() << '\n'; } } return 0; }