src/util/segtree_template.hpp

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

Depends on

src/template.hpp

Code

#include "../template.hpp"


struct Min {
    using S=long;
    S op(S l,S r){return min(l,r);}
    S e(){return LONG_MAX;}
};

struct Sum {
    using S=long;
    S op(S l,S r){return l+r;}
    S e(){return 0;}
};

//f_i(x)=a_ix+b_i, prod(l,r)=f_{r-1}(f_{r-2}(...f_l(x)))
struct LinearF {
    using S=pair<long,long>;
    S op(S l,S r){return {l.fi*r.fi,l.se*r.fi+r.se};}
    S e(){return {1,0};}
};

struct Minid {
    using S=pair<long,int>;
    S op(S l,S r){return min(l,r);}
    S e(){return {LONG_MAX,-1};}
};

#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 2 "src/util/segtree_template.hpp"


struct Min {
    using S=long;
    S op(S l,S r){return min(l,r);}
    S e(){return LONG_MAX;}
};

struct Sum {
    using S=long;
    S op(S l,S r){return l+r;}
    S e(){return 0;}
};

//f_i(x)=a_ix+b_i, prod(l,r)=f_{r-1}(f_{r-2}(...f_l(x)))
struct LinearF {
    using S=pair<long,long>;
    S op(S l,S r){return {l.fi*r.fi,l.se*r.fi+r.se};}
    S e(){return {1,0};}
};

struct Minid {
    using S=pair<long,int>;
    S op(S l,S r){return min(l,r);}
    S e(){return {LONG_MAX,-1};}
};