SlideWindowAggregationDeque
(src/data_structure/slide_window_aggregation_deque.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/data_structure/slide_window_aggregation_deque.hpp"

SlideWindowAggregationDeque

モノイド，つまり

• 結合則: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for all $a, b, c \in S$
• 単位元の存在: $a \cdot e = e \cdot a = a$ for all $a \in S$

を満たす代数構造に対し使用できるデータ構造です．

• dequeの操作
• deque内部の全要素の総積の取得

を償却 $O(1)$ で計算できます．

ただし，これは二項演算 op と単位元取得 e が定数時間で動くと仮定したときの計算量です．
これらが $O(f(n))$ かかる場合は，すべての計算量が $O(f(n))$ 倍となります．

コンストラクタ

SlideWindowAggregationDeque<S, op, e> swag

空のデック swag を作ります．

• 型 S
• 二項演算 S op(S a, S b)
• 単位元 S e()

を定義する必要があります．

例として，Range Minimum Queryなら，

int op(int a, int b) {
    return min(a, b);
}
int e() {
    return (int)1e9;
}
SlideWindowAggregationDeque<int, op, e> swag;

のようになります．

計算量

• $O(1)$

push_front

void swag.push_front(S x)

swag の先頭に $x$ を挿入します．

計算量

• 償却 $O(1)$

push_back

void swag.push_bacl(S x)

swag の末尾に $x$ を挿入します．

計算量

• 償却 $O(1)$

pop_front

void swag.pop_front()

swag から先頭の要素を削除します．

制約

• swag が空でない

計算量

• 償却 $O(1)$

pop_back

void swag.pop_back()

swag から末尾の要素を削除します．

制約

• swag が空でない

計算量

• 償却 $O(1)$

prod

S swag.prod()

op(swag[0], ..., swag[|swag| - 1]) を，モノイドの性質を満たしていると仮定して計算します．

計算量

• $O(1)$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/library_checker/data_structure/deque_operate_all_composite.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename S, auto op, auto e>
struct SlideWindowAggregationDeque {
    void push_front(const S& t) {
        push0(t);
    }
    void push_back(const S& t) {
        push1(t);
    }
    S front() const {
        return a0.empty() ? a1.front() : a0.back();
    }
    S back() const {
        return a1.empty() ? a0.front() : a1.back();
    }
    void pop_front() {
        if(a0.empty()) rebalance();
        assert(!a0.empty());
        a0.pop_back(), r0.pop_back();
    }
    void pop_back() {
        if(a1.empty()) rebalance();
        assert(!a1.empty());
        a1.pop_back(), r1.pop_back();
    }
    S prod() const {
        return op(get0(), get1());
    }

   private:
    vector<S> a0, a1, r0, r1;
    S get0() const {
        return r0.empty() ? e() : r0.back();
    }
    S get1() const {
        return r1.empty() ? e() : r1.back();
    }
    void push0(const S& x) {
        a0.emplace_back(x);
        r0.emplace_back(op(x, get0()));
    }
    void push1(const S& x) {
        a1.emplace_back(x);
        r1.emplace_back(op(get1(), x));
    }
    void rebalance() {
        const int n = a0.size() + a1.size();
        const int s0 = n / 2 + (a0.empty() ? n % 2 : 0);
        vector<S> a{a0};
        reverse(begin(a), end(a));
        copy(begin(a1), end(a1), back_inserter(a));
        a0.clear(), r0.clear();
        a1.clear(), r1.clear();
        for(int i = s0 - 1; i >= 0; --i) push0(a[i]);
        for(int i = s0; i < n; ++i) push1(a[i]);
    }
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/slide_window_aggregation_deque.hpp"
template <typename S, auto op, auto e>
struct SlideWindowAggregationDeque {
    void push_front(const S& t) {
        push0(t);
    }
    void push_back(const S& t) {
        push1(t);
    }
    S front() const {
        return a0.empty() ? a1.front() : a0.back();
    }
    S back() const {
        return a1.empty() ? a0.front() : a1.back();
    }
    void pop_front() {
        if(a0.empty()) rebalance();
        assert(!a0.empty());
        a0.pop_back(), r0.pop_back();
    }
    void pop_back() {
        if(a1.empty()) rebalance();
        assert(!a1.empty());
        a1.pop_back(), r1.pop_back();
    }
    S prod() const {
        return op(get0(), get1());
    }

   private:
    vector<S> a0, a1, r0, r1;
    S get0() const {
        return r0.empty() ? e() : r0.back();
    }
    S get1() const {
        return r1.empty() ? e() : r1.back();
    }
    void push0(const S& x) {
        a0.emplace_back(x);
        r0.emplace_back(op(x, get0()));
    }
    void push1(const S& x) {
        a1.emplace_back(x);
        r1.emplace_back(op(get1(), x));
    }
    void rebalance() {
        const int n = a0.size() + a1.size();
        const int s0 = n / 2 + (a0.empty() ? n % 2 : 0);
        vector<S> a{a0};
        reverse(begin(a), end(a));
        copy(begin(a1), end(a1), back_inserter(a));
        a0.clear(), r0.clear();
        a1.clear(), r1.clear();
        for(int i = s0 - 1; i >= 0; --i) push0(a[i]);
        for(int i = s0; i < n; ++i) push1(a[i]);
    }
};

Back to top page