SWAG(Sliding Window Aggregation)
(data-structure/SWAG.hpp)

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "data-structure/SWAG.hpp"

説明

• SWAG<T,op,e>(int n): Constructor。$O(N)$

• SWAG<T,op,e>(vector<vector<T>> &v): Constructor。$O(N)$

• fold(i, j): 区間$[i,j)$のクエリに答える。前回のクエリを$(i’,j’)$とすると、$i’\leq i$かつ$j’\leq j$である必要がある。$O(1)$

• pop(): 先頭の値を削除する。$O(1)$

Verified with

• test/yosupo/Data-Structure/Queue-Operate-All-Composite.test.cpp

Code

template <class T, T(*op)(const T&,const T&), const T(*e)()>
struct SWAG : deque<T> {
  private:
  T front = e();
  stack<T> back;
  int l = 0, r = 0;
  public:
  SWAG(const int n = 0) : deque<T>(n, e()){}
  SWAG(const deque<T> &v) : deque<T>(v){}
  T fold(const int i, const int j){
    assert(l <= i && i <= j);
    assert(r <= j && j <= (int)(*this).size());
    while(r < j) front = op(front, (*this)[r++]);
    while(l < i){
      if(back.empty()){
        T temp = e();
        for(int u = r - 1; u >= l; u--) back.push(temp = op((*this)[u], temp));
        front = e();
      }
      back.pop();
      l++;
    }
    if(back.empty()) return front;
    return op(back.top(), front);
  }
  void pop(){
    if(!l) fold(l + 1, max(l + 1, r));
    l--; r--;
    (*this).pop_front();
  }
};

#line 1 "data-structure/SWAG.hpp"
template <class T, T(*op)(const T&,const T&), const T(*e)()>
struct SWAG : deque<T> {
  private:
  T front = e();
  stack<T> back;
  int l = 0, r = 0;
  public:
  SWAG(const int n = 0) : deque<T>(n, e()){}
  SWAG(const deque<T> &v) : deque<T>(v){}
  T fold(const int i, const int j){
    assert(l <= i && i <= j);
    assert(r <= j && j <= (int)(*this).size());
    while(r < j) front = op(front, (*this)[r++]);
    while(l < i){
      if(back.empty()){
        T temp = e();
        for(int u = r - 1; u >= l; u--) back.push(temp = op((*this)[u], temp));
        front = e();
      }
      back.pop();
      l++;
    }
    if(back.empty()) return front;
    return op(back.top(), front);
  }
  void pop(){
    if(!l) fold(l + 1, max(l + 1, r));
    l--; r--;
    (*this).pop_front();
  }
};

Back to top page