SWAG
(lib/data_structure/swag.hpp)

• View this file on GitHub
• Last update: 2024-11-15 15:44:55+09:00
• Include: #include "lib/data_structure/swag.hpp"

SWAG

使い方

• SWAG<T>(op): SWAG を構築します。
• fold(): 要素全てに op を適用させた値を計算します。
• push(x): x を先頭に追加します。
• pop(): 先頭の要素を削除します。

計算量

• fold(): $\mathrm{O}(1)$
• push(x): $\mathrm{O}(1)$
• pop(): 償却 $\mathrm{O}(1)$

Verified with

• test/library_checker/data_structure/queue_operate_all_composite.test.cpp

Code

#pragma once

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

#include <stack>
#include <cassert>

template <typename T, T (*op)(T, T)>
struct SWAG{
private:
    struct node{
    public:
        T val, sum;
        node(const T &val, const T &sum) : val(val), sum(sum) {}
    };

    std::stack<node> front_stack, back_stack;

public:
    SWAG() : front_stack(), back_stack() {}

    bool empty(){
        return front_stack.empty() && back_stack.empty();
    }

    size_t size(){
        return front_stack.size() + back_stack.size();
    }

    T fold(){
        if(front_stack.empty()){
            return back_stack.top().sum;
        } else if(back_stack.empty()){
            return front_stack.top().sum;
        } else{
            return op(front_stack.top().sum, back_stack.top().sum);
        }
    }

    void push(const T &x){
        if(back_stack.empty()){
            back_stack.emplace(x, x);
        } else{
            T s = op(back_stack.top().sum, x);
            back_stack.emplace(x, s);
        }
    }

    void pop(){
        assert(!empty());
        if(front_stack.empty()){
            front_stack.emplace(back_stack.top().val, back_stack.top().val);
            back_stack.pop();
            while(!back_stack.empty()){
                T s = op(back_stack.top().val, front_stack.top().sum);
                front_stack.emplace(back_stack.top().val, s);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
};

#line 2 "lib/data_structure/swag.hpp"

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

#include <stack>
#include <cassert>

template <typename T, T (*op)(T, T)>
struct SWAG{
private:
    struct node{
    public:
        T val, sum;
        node(const T &val, const T &sum) : val(val), sum(sum) {}
    };

    std::stack<node> front_stack, back_stack;

public:
    SWAG() : front_stack(), back_stack() {}

    bool empty(){
        return front_stack.empty() && back_stack.empty();
    }

    size_t size(){
        return front_stack.size() + back_stack.size();
    }

    T fold(){
        if(front_stack.empty()){
            return back_stack.top().sum;
        } else if(back_stack.empty()){
            return front_stack.top().sum;
        } else{
            return op(front_stack.top().sum, back_stack.top().sum);
        }
    }

    void push(const T &x){
        if(back_stack.empty()){
            back_stack.emplace(x, x);
        } else{
            T s = op(back_stack.top().sum, x);
            back_stack.emplace(x, s);
        }
    }

    void pop(){
        assert(!empty());
        if(front_stack.empty()){
            front_stack.emplace(back_stack.top().val, back_stack.top().val);
            back_stack.pop();
            while(!back_stack.empty()){
                T s = op(back_stack.top().val, front_stack.top().sum);
                front_stack.emplace(back_stack.top().val, s);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
};

Back to top page