Slope Trick
(DataStructure/slopetrick.hpp)

• View this file on GitHub
• Last update: 2022-02-05 01:38:09+09:00
• Include: #include "DataStructure/slopetrick.hpp"

使い方

SlopeTrick(): 空のデータ構造を作成。
T getmin(): 凸関数の最小値。
pair<T,T> argmin(): 凸関数の最小値となる $x$ の閉区間。
void addConst(T a): $y=a$ を凸関数に加算。
void addx_a(T a): $y=\max(0,x-a)$ を凸関数に加算。
void adda_x(T a): $y=\max(0,a-x)$ を凸関数に加算。
void addAbs(T a): $y=|x-a|$ を凸関数に加算。
void chminRight(): 正の方向に向かって累積最小値を取る。
void chminLeft(): 負の方向に向かって累積最小値を取る。
void shiftLeft(T a): $g(x)=\max_{t \in [x-a,x]} f(t)(0 \leq a),\min_{t \in [x,x-a]} f(t)(0>a)$ を計算。
void shiftRight(T a): $g(x)=\min_{t \in [x-a,x]} f(t)(0 \leq a),\max_{t \in [x,x-a]} f(t)(0>a)$ を計算。
void shift(T a): $g(x)=f(x-a)$ を計算。
T eval(T x_0): $x=x_0$ での値を計算。(破壊的)

Code

#pragma once

template<typename T,T mx>struct SlopeTrick{
    T mn=0,addL=0,addR=0;
    priority_queue<T> L;
    priority_queue<T,vector<T>,greater<T>> R;
    SlopeTrick(){
        L.push(-mx);
        R.push(mx);
    }
    T getmin(){return mn;}
    pair<T,T> argmin(){
        return {L.top()+addL,R.top()+addR};
    }
    void addConst(T a){mn+=a;}
    void addx_a(T a){
        mn+=max(T(0),L.top()+addL-a);
        L.push(a-addL);
        R.push(L.top()+addL-addR);
        L.pop();
    }
    void adda_x(T a){
        mn+=max(T(0),a-(R.top()+addR));
        R.push(a-addR);
        L.push(R.top()+addR-addL);
        R.pop();
    }
    void addAbs(T a){
        addx_a(a);
        adda_x(a);
    }
    void chminRight(){
        priority_queue<T,vector<T>,greater<T>> nxt;
        nxt.push(mx);
        swap(R,nxt);
        addR=0;
    }
    void chminLeft(){
        priority_queue<T> nxt;
        nxt.push(-mx);
        swap(L,nxt);
        addL=0;
    }
    void shiftLeft(T a){
        addL+=a;
    }
    void shiftRight(T a){
        addR+=a;
    }
    void shift(T a){
        shiftRight(a);
        shiftLeft(a);
    }
    T eval(T x_0){
        T y=mn;
        while(!L.empty()){
            auto x=L.top();
            L.pop();
            y+=max(T(0),(x+addL)-x_0);
        }
        while(!R.empty()){
            auto x=R.top();
            R.pop();
            y+=max(T(0),x_0-(x+addR));
        }
        return y;
    }
};

/**
 * @brief Slope Trick
 * @docs docs/slopetrick.md
 */

#line 2 "DataStructure/slopetrick.hpp"

template<typename T,T mx>struct SlopeTrick{
    T mn=0,addL=0,addR=0;
    priority_queue<T> L;
    priority_queue<T,vector<T>,greater<T>> R;
    SlopeTrick(){
        L.push(-mx);
        R.push(mx);
    }
    T getmin(){return mn;}
    pair<T,T> argmin(){
        return {L.top()+addL,R.top()+addR};
    }
    void addConst(T a){mn+=a;}
    void addx_a(T a){
        mn+=max(T(0),L.top()+addL-a);
        L.push(a-addL);
        R.push(L.top()+addL-addR);
        L.pop();
    }
    void adda_x(T a){
        mn+=max(T(0),a-(R.top()+addR));
        R.push(a-addR);
        L.push(R.top()+addR-addL);
        R.pop();
    }
    void addAbs(T a){
        addx_a(a);
        adda_x(a);
    }
    void chminRight(){
        priority_queue<T,vector<T>,greater<T>> nxt;
        nxt.push(mx);
        swap(R,nxt);
        addR=0;
    }
    void chminLeft(){
        priority_queue<T> nxt;
        nxt.push(-mx);
        swap(L,nxt);
        addL=0;
    }
    void shiftLeft(T a){
        addL+=a;
    }
    void shiftRight(T a){
        addR+=a;
    }
    void shift(T a){
        shiftRight(a);
        shiftLeft(a);
    }
    T eval(T x_0){
        T y=mn;
        while(!L.empty()){
            auto x=L.top();
            L.pop();
            y+=max(T(0),(x+addL)-x_0);
        }
        while(!R.empty()){
            auto x=R.top();
            R.pop();
            y+=max(T(0),x_0-(x+addR));
        }
        return y;
    }
};

/**
 * @brief Slope Trick
 * @docs docs/slopetrick.md
 */

Back to top page