ds/SWAD.h

• View this file on GitHub
• Last update: 2025-11-21 16:12:02+07:00

Verified with

• tests/Deque_Operate_All_Composite.test.cpp

Code

template <class T, class F>
struct SWAD {
  vector<T> a0, a1, r0, r1;
  F f;
  T I;
  SWAD(F f, T i) : f(f), I(i) {}

 private:
  T get0() const { return r0.empty() ? I : r0.back(); }
  T get1() const { return r1.empty() ? I : r1.back(); }

  void push0(const T& x) {
    a0.eb(x), r0.eb(f(x, get0()));
  }
  void push1(const T& x) {
    a1.eb(x), r1.eb(f(get1(), x));
  }
  void rebalance() {
    int n = a0.size() + a1.size();
    int s0 = n / 2 + (a0.empty() ? n % 2 : 0);
    vector<T> a{a0};
    reverse(all(a));
    copy(all(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]);
  }

 public:
  void push_front(const T& t) { push0(t); }
  void push_back(const T& t) { push1(t); }
  T front() const { return a0.empty() ? a1.front() : a0.back(); }
  T 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();
  }
  T query() { return f(get0(), get1()); }
};

#line 1 "ds/SWAD.h"
template <class T, class F>
struct SWAD {
  vector<T> a0, a1, r0, r1;
  F f;
  T I;
  SWAD(F f, T i) : f(f), I(i) {}

 private:
  T get0() const { return r0.empty() ? I : r0.back(); }
  T get1() const { return r1.empty() ? I : r1.back(); }

  void push0(const T& x) {
    a0.eb(x), r0.eb(f(x, get0()));
  }
  void push1(const T& x) {
    a1.eb(x), r1.eb(f(get1(), x));
  }
  void rebalance() {
    int n = a0.size() + a1.size();
    int s0 = n / 2 + (a0.empty() ? n % 2 : 0);
    vector<T> a{a0};
    reverse(all(a));
    copy(all(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]);
  }

 public:
  void push_front(const T& t) { push0(t); }
  void push_back(const T& t) { push1(t); }
  T front() const { return a0.empty() ? a1.front() : a0.back(); }
  T 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();
  }
  T query() { return f(get0(), get1()); }
};

Back to top page