SlideWindowAggregation
(src/data_structure/slide_window_aggregation.hpp)

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

SlideWindowAggregation

モノイド，つまり

• 結合則: $(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$

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

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

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

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

コンストラクタ

SlideWindowAggregation<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;
}
SlideWindowAggregation<int, op, e> swag;

のようになります．

計算量

• $O(1)$

push

void swag.push(S x)

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

計算量

• 償却 $O(1)$

pop

void swag.pop()

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/queue_operate_all_composite.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename S, auto op, auto e>
struct SlideWindowAggregation {
    SlideWindowAggregation()
        : f0(e()), f1(e()) {}
    void push(const S& x) {
        if(a0.empty()) {
            push_s0(x);
            transfer();
        } else {
            push_s1(x);
        }
    }
    void pop() {
        if(a0.empty()) transfer();
        a0.pop_back();
        r0.pop_back();
        f0 = r0.empty() ? e() : r0.back();
    }
    S prod() const {
        return op(f0, f1);
    }

   private:
    vector<S> a0, a1, r0, r1;
    S f0, f1;
    void push_s0(const S& x) {
        a0.emplace_back(x);
        r0.emplace_back(f0 = op(x, f0));
    }
    void push_s1(const S& x) {
        a1.emplace_back(x);
        r1.emplace_back(f1 = op(f1, x));
    }
    void transfer() {
        while(!a1.empty()) {
            push_s0(a1.back());
            a1.pop_back();
        }
        while(!r1.empty()) r1.pop_back();
        f1 = e();
    }
};

#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.hpp"
template <typename S, auto op, auto e>
struct SlideWindowAggregation {
    SlideWindowAggregation()
        : f0(e()), f1(e()) {}
    void push(const S& x) {
        if(a0.empty()) {
            push_s0(x);
            transfer();
        } else {
            push_s1(x);
        }
    }
    void pop() {
        if(a0.empty()) transfer();
        a0.pop_back();
        r0.pop_back();
        f0 = r0.empty() ? e() : r0.back();
    }
    S prod() const {
        return op(f0, f1);
    }

   private:
    vector<S> a0, a1, r0, r1;
    S f0, f1;
    void push_s0(const S& x) {
        a0.emplace_back(x);
        r0.emplace_back(f0 = op(x, f0));
    }
    void push_s1(const S& x) {
        a1.emplace_back(x);
        r1.emplace_back(f1 = op(f1, x));
    }
    void transfer() {
        while(!a1.empty()) {
            push_s0(a1.back());
            a1.pop_back();
        }
        while(!r1.empty()) r1.pop_back();
        f1 = e();
    }
};

Back to top page