src/structure/swag.hpp

• View this file on GitHub
• Last update: 2025-12-30 15:03:15+09:00
• Include: #include "src/structure/swag.hpp"

Depends on

• src/template.hpp

Verified with

• src/test/yosupo_queue_operate_all_composite.cpp

Code

#pragma once
#include "../template.hpp"

template<class S,S (*op)(S,S),S (*e)()>
struct SWAG {
    vector<S> r,ld,rd;
    SWAG():r(1,e()),ld(1,e()),rd(1,e()){}

    void push(S s){
        r.push_back(s);
        rd.push_back(op(rd.back(),s));
    }
    void pop(){
        if(si(ld)==1){
            while(si(r)>=2){
                ld.push_back(op(r.back(),ld.back()));
                r.pop_back();
                rd.pop_back();
            }
        }
        ld.pop_back();
        assert(si(ld));
    }
    S get(){
        return op(ld.back(),rd.back());
    }
    pair<S,S> get_lr(){
        return {ld.back(),rd.back()};
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/structure/swag.hpp"

template<class S,S (*op)(S,S),S (*e)()>
struct SWAG {
    vector<S> r,ld,rd;
    SWAG():r(1,e()),ld(1,e()),rd(1,e()){}

    void push(S s){
        r.push_back(s);
        rd.push_back(op(rd.back(),s));
    }
    void pop(){
        if(si(ld)==1){
            while(si(r)>=2){
                ld.push_back(op(r.back(),ld.back()));
                r.pop_back();
                rd.pop_back();
            }
        }
        ld.pop_back();
        assert(si(ld));
    }
    S get(){
        return op(ld.back(),rd.back());
    }
    pair<S,S> get_lr(){
        return {ld.back(),rd.back()};
    }
};

Back to top page