< askr58さんのAI生成コード置き場

slopetrick

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

// This code was generated by Gemini outside of active contest hours.
// Reference: slope trick (1) 解説編 | maspyのHP
// URL: https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8#toc7
template<typename T>
struct SlopeTrick {
    // 無限大を表す定数（番兵として使用）
    const T INF = std::numeric_limits<T>::max() / 3;

    T min_f; // 関数の最小値
    std::priority_queue<T> L; // 傾きが0以下の領域における変化点（最大ヒープ）
    std::priority_queue<T, std::vector<T>, std::greater<T>> R; // 傾きが0以上の領域における変化点（最小ヒープ）
    T add_l, add_r; // 遅延加算用タグ（L, R 全体への一律加算を管理）

    // コンストラクタ
    // 初期状態は f(x) = 0 (すべての x で傾き 0、最小値 0)
    SlopeTrick() : min_f(0), add_l(0), add_r(0) {
        // 必要に応じて番兵を入れる実装もありますが、
        // 今回は空の状態を許容し、アクセス時にチェック・補正する方針で実装します。
    }

    // L の最大値（実際の値）を取得
    // L が空の場合は -INF を返す
    T get_max_l() const {
        if (L.empty()) return -INF;
        return L.top() + add_l;
    }

    // R の最小値（実際の値）を取得
    // R が空の場合は INF を返す
    T get_min_r() const {
        if (R.empty()) return INF;
        return R.top() + add_r;
    }

    // ---------------------------------------------------------
    // 可能な操作 (Basic Operations)
    // ---------------------------------------------------------

    // 最小値の取得: min f(x)
    // 計算量: O(1)
    T get_min() const {
        return min_f;
    }

    // 最小値を与える x の範囲 [left, right] を取得 (argmin f(x))
    // 計算量: O(1)
    // 戻り値: {min_range_left, min_range_right}
    std::pair<T, T> get_argmin() const {
        return {get_max_l(), get_min_r()};
    }

    // 定数関数の加算: f(x) <- f(x) + c
    // 計算量: O(1)
    void add_const(T c) {
        min_f += c;
    }

    // (x - a)_+ の加算: f(x) <- f(x) + max(0, x - a)
    // グラフの右側の傾きが増加する操作
    // 計算量: O(log N)
    void add_x_minus_a(T a) {
        // 1. 最小値の更新
        // 更新前の L の最大値 l0 と a を比較し、min_f を更新
        // max(0, l0 - a) を加算
        T l0 = get_max_l();
        min_f += std::max<T>(0, l0 - a);

        // 2. 変化点の更新
        // a を L に追加し、L の最大値を R に移すことで整合性を保つ
        L.push(a - add_l);
        
        T moved_val = L.top() + add_l;
        L.pop();
        
        R.push(moved_val - add_r);
    }

    // (a - x)_+ の加算: f(x) <- f(x) + max(0, a - x)
    // グラフの左側の傾きが減少する（負の方向に傾きがつく）操作
    // 計算量: O(log N)
    void add_a_minus_x(T a) {
        // 1. 最小値の更新
        // 更新前の R の最小値 r0 と a を比較し、min_f を更新
        // max(0, a - r0) を加算
        T r0 = get_min_r();
        min_f += std::max<T>(0, a - r0);

        // 2. 変化点の更新
        // a を R に追加し、R の最小値を L に移す
        R.push(a - add_r);
        
        T moved_val = R.top() + add_r;
        R.pop();
        
        L.push(moved_val - add_l);
    }

    // |x - a| の加算: f(x) <- f(x) + |x - a|
    // 計算量: O(log N)
    // |x - a| = (x - a)_+ + (a - x)_+ であるため、両方を実行すればよい
    void add_abs(T a) {
        add_x_minus_a(a);
        add_a_minus_x(a);
    }

    // 累積 min (左側): g(x) = min_{y <= x} f(y)
    // 右側の傾き増加部分（R）をすべて削除することで、右側を平坦にする
    // 計算量: O(1) ※内部のコンテナの実装依存、通常クリアは高速
    void clear_right() {
        while (!R.empty()) R.pop();
    }

    // 累積 min (右側): g(x) = min_{y >= x} f(y)
    // 左側の傾き減少部分（L）をすべて削除することで、左側を平坦にする
    // 計算量: O(1)
    void clear_left() {
        while (!L.empty()) L.pop();
    }

    // ---------------------------------------------------------
    // 拡張 (Extensions)
    // ---------------------------------------------------------

    // 平行移動: f(x) <- f(x - a)
    // グラフ全体を右に a ずらす
    // 計算量: O(1)
    void translate(T a) {
        add_l += a;
        add_r += a;
    }

    // スライド最小値 (Sliding Window Minimum):
    // g(x) = min_{y in [x - b, x - a]} f(y)  (ただし a <= b)
    // 解説:
    // これは L を a ずらし、R を b ずらす操作に対応する
    // 計算量: O(1)
    void sliding_window_minimum(T a, T b) {
        if (a > b) return; // 不正な区間なら何もしない（あるいはassert）
        add_l += a;
        add_r += b;
    }
}// End of Gemini's implementation.