模板集合

Basic

通用模板

#include 
using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pii;

template
inline T read(){
    T x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}

#define rdi read
#define rdll read
#define fi first
#define se second
#define pb push_back
#define mp make_pair

int main(){
#ifdef LOCAL
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    return 0;
}

读入优化

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

DS

Segment Tree Beats

区间取 min，区间加，区间求和。

struct Node{
    ll mx,smx,sum;
    int cnt;
    friend Node operator + (Node a,Node b){
        if(!a.cnt1) return b;
        if(!b.cnt1) return a;
        if(a.mxb.mx) return {a.mx,max(a.smx,b.mx),a.sum+b.sum,a.cnt};
        else return {a.mx,max(a.smx,b.smx),a.sum+b.sum,a.cnt+b.cnt};
    }
}t[N*4];
ll tmx[N*4],tsum[N*4];
void pushup(int now) {t[now]=t[lson]+t[rson];}
void upd1(int now,ll t1){
    if(t[now].mxy||val>=t[now].mx) return;
    if(x<=l&&r<=y&&val>t[now].smx) return upd1(now,val);
    if(l==r) {t[now].mx=min(t[now].mx,val),t[now].sum=t[now].mx;return;}
    pushdown(now);
    if(x<=mid) chkmin(lson,l,mid,x,y,val);
    if(y>mid) chkmin(rson,mid+1,r,x,y,val);
    pushup(now);
}
void query(){
    //与普通线段树相同
}

李超树

支持插入直线，查询，合并。

struct Line{
    ll k,b;
    ll operator ()(ll x) const{return k*x+b;}
};

struct SGT{
#define lson (t[now].ls)
#define rson (t[now].rs)
#define mid ((l+r)>>1)
    struct Node{Line cur;int ls,rs;}t[N*60];
    int tot;

    int newnode(){
        t[++tot]={{0,INFl},0,0};
        return tot;
    }
    void insert(int &now,int l,int r,Line x){
        if(!now) now=newnode();
        if(t[now].cur(mid)>x(mid)) swap(t[now].cur,x);
        if(l==r) return;
        if(x(l)

struct SGT{
#define lson (now<<1)
#define rson (now<<1|1)
#define mid ((l+r)>>1)
    struct Node{ll mx,hmx,ad,h_ad;}t[N*4];
    void upd(int now,ll ad,ll h_ad){
        t[now].hmx=max(t[now].mx+h_ad,t[now].hmx),t[now].mx+=ad;
        t[now].h_ad=max(t[now].h_ad,t[now].ad+h_ad),t[now].ad+=ad;
    }
    void pushdown(int now){
        if(t[now].ad||t[now].h_ad){
            upd(lson,t[now].ad,t[now].h_ad),upd(rson,t[now].ad,t[now].h_ad);
            t[now].ad=t[now].h_ad=0;
        }
    }
    void pushup(int now){
        t[now].mx=max(t[lson].mx,t[rson].mx);
        t[now].hmx=max({t[now].mx,t[lson].hmx,t[rson].hmx});
    }

    void build(int now,int l,int r){
        t[now].mx=t[now].hmx=-INFl;
        if(l==r) return;
        build(lson,l,mid);build(rson,mid+1,r);
    }
    void add(int now,int l,int r,int x,int y,ll val){
        if(x<=l&&r<=y) {upd(now,val,max(val,0ll));return;}
        pushdown(now);
        if(x<=mid) add(lson,l,mid,x,y,val);
        if(y>mid) add(rson,mid+1,r,x,y,val);
        pushup(now);
    }
    void set(int now,int l,int r,int x,ll val){
        if(l==r){
            t[now].mx=val;
            t[now].hmx=max(t[now].hmx,t[now].mx);
            return;
        }
        pushdown(now);
        x<=mid?set(lson,l,mid,x,val):set(rson,mid+1,r,x,val);
        pushup(now);
    }
    ll query(int now,int l,int r,int x,int y){
        if(x<=l&&r<=y) return t[now].hmx;
        ll ret=-INFl;pushdown(now);
        if(x<=mid) ret=max(ret,query(lson,l,mid,x,y));
        if(y>mid) ret=max(ret,query(rson,mid+1,r,x,y));
        return ret;
    }
#undef lson
#undef rson
#undef mid
};