SWAG
(Datastructure/swag.hpp)

• View this file on GitHub
• Last update: 2024-07-06 20:37:29+09:00
• Include: #include "Datastructure/swag.hpp"

概要

値の集約ができるdeque。 名称について、SWAGと呼ばれる事が多い？ 参考 : https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1

コンストラクタ

SWAG<S, op> swag … 空のswagを生成する。セグ木における単位元が必要無いことに注意。計算量 $O(1)$

• S モノイドの型。

• op S (*op) (S, S) モノイドを2つ受け取り、その演算結果を返す関数を渡す。なお、演算に可換性は要求しない。

関数

全て、計算量は償却 $O(1)$

• dequeのpush/pop/size/empty… popは、要素数が0だとassertで落ちる。

• S get()… swagに入っているモノイドの集約結果を返す。要素数が0だとassertで落ちる。

Verified with

• verify/Datastructure_swag.test.cpp
• verify/Datastructure_swag_more.test.cpp
• 砂場/swag.test.cpp

Code

template<class S, S (*op)(S, S)>  struct SWAG {
    struct foldable_stack {
        stack<S> data;
        stack<S> res;
        foldable_stack(){}

        void push(S a, int type) {//type == 1 : 配列の右に追加、つまりR  type == 0 : 配列の左に追加、つまりL 
            data.push(a);
            if(!res.empty()) {
               if(type == 0) res.push(op(a, res.top()));//resが空ならそれを入れる
               else res.push(op(res.top(), a));
            }
            else res.push(a);
            return;
        }

        void pop() {
            assert(!data.empty());
            data.pop();
            res.pop();
            return;
        }

        S top() const {
            assert(!data.empty());
            return data.top(); 
        }

        S get() const { 
            assert(!data.empty());
            return res.top(); 
        }

        bool empty() {return data.empty();}
        int size() {return data.size();}
    };

    
    SWAG() {}
    foldable_stack L, R;
    private:

      void move(foldable_stack& s, foldable_stack& t, int type) {//sの要素を半分tの要素に移す。ここで、type == 0 : s = L, t = R  type == 1 s = R, t = L
        assert(t.empty());
        int oth = 1 - type;
        stack<S> tmp;
        while(int(s.size()) - int(tmp.size()) > 1) tmp.push(s.top()), s.pop();
        while(!s.empty()) t.push(s.top(), oth), s.pop(); 
        while(!tmp.empty()) s.push(tmp.top(), type), tmp.pop(); 
      }
    
    public:
      void push_front(S a) {
          L.push(a, 0);
      }
  
      void push_back(S a) {
          R.push(a, 1);
      }
  
      void pop_front() {
          assert(!L.empty() || !R.empty());
          if(L.empty()) move(R, L, 1);
          L.pop();
      }
  
      void pop_back() {
          assert(!L.empty() || !R.empty());
          if(R.empty()) move(L, R, 0);
          R.pop();
      }
  

      S get()  {
        assert(!L.empty() || !R.empty());
        if(L.empty()) return R.get();
        if(R.empty()) return L.get();
        return op(L.get(), R.get());
      }

      int size() {
        return L.size() + R.size();
      }

      bool empty() {
        return size() == 0;
      }
};


/*
@brief SWAG
@docs doc/swag.md
*/

#line 1 "Datastructure/swag.hpp"

template<class S, S (*op)(S, S)>  struct SWAG {
    struct foldable_stack {
        stack<S> data;
        stack<S> res;
        foldable_stack(){}

        void push(S a, int type) {//type == 1 : 配列の右に追加、つまりR  type == 0 : 配列の左に追加、つまりL 
            data.push(a);
            if(!res.empty()) {
               if(type == 0) res.push(op(a, res.top()));//resが空ならそれを入れる
               else res.push(op(res.top(), a));
            }
            else res.push(a);
            return;
        }

        void pop() {
            assert(!data.empty());
            data.pop();
            res.pop();
            return;
        }

        S top() const {
            assert(!data.empty());
            return data.top(); 
        }

        S get() const { 
            assert(!data.empty());
            return res.top(); 
        }

        bool empty() {return data.empty();}
        int size() {return data.size();}
    };

    
    SWAG() {}
    foldable_stack L, R;
    private:

      void move(foldable_stack& s, foldable_stack& t, int type) {//sの要素を半分tの要素に移す。ここで、type == 0 : s = L, t = R  type == 1 s = R, t = L
        assert(t.empty());
        int oth = 1 - type;
        stack<S> tmp;
        while(int(s.size()) - int(tmp.size()) > 1) tmp.push(s.top()), s.pop();
        while(!s.empty()) t.push(s.top(), oth), s.pop(); 
        while(!tmp.empty()) s.push(tmp.top(), type), tmp.pop(); 
      }
    
    public:
      void push_front(S a) {
          L.push(a, 0);
      }
  
      void push_back(S a) {
          R.push(a, 1);
      }
  
      void pop_front() {
          assert(!L.empty() || !R.empty());
          if(L.empty()) move(R, L, 1);
          L.pop();
      }
  
      void pop_back() {
          assert(!L.empty() || !R.empty());
          if(R.empty()) move(L, R, 0);
          R.pop();
      }
  

      S get()  {
        assert(!L.empty() || !R.empty());
        if(L.empty()) return R.get();
        if(R.empty()) return L.get();
        return op(L.get(), R.get());
      }

      int size() {
        return L.size() + R.size();
      }

      bool empty() {
        return size() == 0;
      }
};


/*
@brief SWAG
@docs doc/swag.md
*/

Back to top page