This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#include "deque/sliding_window.hpp"
#include <cassert> #include <cstdio> #include <functional> #include <iostream> #include <stack> //=== // LIBRARY SECTION // #include <stack> // #include <cassert> template <class SemiGroup, class OP = std::function<SemiGroup(SemiGroup, SemiGroup)> > struct SlidingWindow { // first:original data, second:sum using Stack = std::stack<std::pair<SemiGroup, SemiGroup> >; const OP merge; Stack front_st, back_st; SlidingWindow(const OP &f) : merge(f){}; inline SemiGroup fold() { assert(!empty()); if (front_st.empty()) return back_st.top().second; else if (back_st.empty()) return front_st.top().second; else return merge(front_st.top().second, back_st.top().second); }; inline void push_front(SemiGroup d) { if (front_st.empty()) front_st.emplace(d, d); else front_st.emplace(d, merge(d, front_st.top().second)); }; inline void push_back(SemiGroup d) { if (back_st.empty()) back_st.emplace(d, d); else back_st.emplace(d, merge(back_st.top().second, d)); }; void pop_front() { assert(!empty()); if (front_st.empty()) { Stack buff; while (buff.size() + 1 < back_st.size()) { buff.push(back_st.top()); back_st.pop(); } while (!back_st.empty()) { push_front(back_st.top().first); back_st.pop(); } while (!buff.empty()) { push_back(buff.top().first); buff.pop(); } } front_st.pop(); }; void pop_back() { assert(!empty()); if (back_st.empty()) { Stack buff; while (buff.size() + 1 < front_st.size()) { buff.push(front_st.top()); front_st.pop(); } while (!front_st.empty()) { push_back(front_st.top().first); front_st.pop(); } while (!buff.empty()) { push_front(buff.top().first); buff.pop(); } } back_st.pop(); }; inline bool empty() { return size() == 0; }; inline size_t size() { return front_st.size() + back_st.size(); }; }; //===
#line 1 "deque/sliding_window.hpp" #include <cassert> #include <cstdio> #include <functional> #include <iostream> #include <stack> //=== // LIBRARY SECTION // #include <stack> // #include <cassert> template <class SemiGroup, class OP = std::function<SemiGroup(SemiGroup, SemiGroup)> > struct SlidingWindow { // first:original data, second:sum using Stack = std::stack<std::pair<SemiGroup, SemiGroup> >; const OP merge; Stack front_st, back_st; SlidingWindow(const OP &f) : merge(f){}; inline SemiGroup fold() { assert(!empty()); if (front_st.empty()) return back_st.top().second; else if (back_st.empty()) return front_st.top().second; else return merge(front_st.top().second, back_st.top().second); }; inline void push_front(SemiGroup d) { if (front_st.empty()) front_st.emplace(d, d); else front_st.emplace(d, merge(d, front_st.top().second)); }; inline void push_back(SemiGroup d) { if (back_st.empty()) back_st.emplace(d, d); else back_st.emplace(d, merge(back_st.top().second, d)); }; void pop_front() { assert(!empty()); if (front_st.empty()) { Stack buff; while (buff.size() + 1 < back_st.size()) { buff.push(back_st.top()); back_st.pop(); } while (!back_st.empty()) { push_front(back_st.top().first); back_st.pop(); } while (!buff.empty()) { push_back(buff.top().first); buff.pop(); } } front_st.pop(); }; void pop_back() { assert(!empty()); if (back_st.empty()) { Stack buff; while (buff.size() + 1 < front_st.size()) { buff.push(front_st.top()); front_st.pop(); } while (!front_st.empty()) { push_back(front_st.top().first); front_st.pop(); } while (!buff.empty()) { push_front(buff.top().first); buff.pop(); } } back_st.pop(); }; inline bool empty() { return size() == 0; }; inline size_t size() { return front_st.size() + back_st.size(); }; }; //===