Foldable Deque
(data-structure/foldable_deque.hpp)

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Include: #include "data-structure/foldable_deque.hpp"

Description

Stack 2つで deque をシミュレートする技法で，半群要素の総積の計算が可能な deque を作ることができる． Sliding window aggregation の deque 版である．

Operations

• void push_front(T x)
  • $x$ を deque の先頭に追加する
  • 時間計算量: $O(1)$
• void push_back(T x)
  • $x$ を deque の末尾に追加する
  • 時間計算量: $O(1)$
• void pop_front()
  • deque の先頭要素を削除する
  • 時間計算量: $\mathrm{amortized}\ O(1)$
• void pop_back()
  • deque の先頭要素を削除する
  • 時間計算量: $\mathrm{amortized}\ O(1)$
• bool empty()
  • deque が空かどうか判定する
  • 時間計算量: $O(1)$
• T fold()
  • deque の要素の総積を返す
  • 時間計算量: $O(1)$

Reference

• Amortize analysis of Deque with 2 Stack - slideshare

Verified with

• test/yosupo/deque_operate_all_composite.test.cpp

Code

#pragma once
#include <cassert>
#include <stack>
#include <utility>
#include <vector>

template <typename S>
class FoldableDeque {
    using T = typename S::T;

   public:
    void push_front(const T& x) {
        if (front.empty())
            front.emplace(x, x);
        else
            front.emplace(x, S::op(x, front.top().second));
    }

    void push_back(const T& x) {
        if (back.empty())
            back.emplace(x, x);
        else
            back.emplace(x, S::op(back.top().second, x));
    }

    void pop_front() {
        assert(!empty());
        if (front.empty()) {
            std::vector<T> xs;
            while (!back.empty()) {
                xs.push_back(back.top().first);
                back.pop();
            }
            int n = xs.size();
            for (int i = n / 2; i < n; ++i) push_front(xs[i]);
            for (int i = n / 2 - 1; i >= 0; --i) push_back(xs[i]);
        }
        front.pop();
    }

    void pop_back() {
        assert(!empty());
        if (back.empty()) {
            std::vector<T> xs;
            while (!front.empty()) {
                xs.push_back(front.top().first);
                front.pop();
            }
            int n = xs.size();
            for (int i = n / 2 - 1; i >= 0; --i) push_front(xs[i]);
            for (int i = n / 2; i < n; ++i) push_back(xs[i]);
        }
        back.pop();
    }

    bool empty() const { return front.empty() && back.empty(); }

    T fold() const {
        assert(!empty());
        if (front.empty()) return back.top().second;
        if (back.empty()) return front.top().second;
        return S::op(front.top().second, back.top().second);
    }

   private:
    std::stack<std::pair<T, T>> front, back;
};

#line 2 "data-structure/foldable_deque.hpp"
#include <cassert>
#include <stack>
#include <utility>
#include <vector>

template <typename S>
class FoldableDeque {
    using T = typename S::T;

   public:
    void push_front(const T& x) {
        if (front.empty())
            front.emplace(x, x);
        else
            front.emplace(x, S::op(x, front.top().second));
    }

    void push_back(const T& x) {
        if (back.empty())
            back.emplace(x, x);
        else
            back.emplace(x, S::op(back.top().second, x));
    }

    void pop_front() {
        assert(!empty());
        if (front.empty()) {
            std::vector<T> xs;
            while (!back.empty()) {
                xs.push_back(back.top().first);
                back.pop();
            }
            int n = xs.size();
            for (int i = n / 2; i < n; ++i) push_front(xs[i]);
            for (int i = n / 2 - 1; i >= 0; --i) push_back(xs[i]);
        }
        front.pop();
    }

    void pop_back() {
        assert(!empty());
        if (back.empty()) {
            std::vector<T> xs;
            while (!front.empty()) {
                xs.push_back(front.top().first);
                front.pop();
            }
            int n = xs.size();
            for (int i = n / 2 - 1; i >= 0; --i) push_front(xs[i]);
            for (int i = n / 2; i < n; ++i) push_back(xs[i]);
        }
        back.pop();
    }

    bool empty() const { return front.empty() && back.empty(); }

    T fold() const {
        assert(!empty());
        if (front.empty()) return back.top().second;
        if (back.empty()) return front.top().second;
        return S::op(front.top().second, back.top().second);
    }

   private:
    std::stack<std::pair<T, T>> front, back;
};

Back to top page