슬로프 트릭 – 학습

1강 볼록 함수의 기울기 변화점 DP 공식

동기

DP 값 함수 $$f_i(x)$$ 가 항상 볼록 조각별 선형(piecewise linear convex) 함수가 되는 문제가 많다. 예: 각 위치에서 값을 $\pm 1$ 조정하는 비용의 누적 최소화, 비감소 수열로 만들기 최소비용 등. 함수 전체를 들고 다니면 비싸지만, 볼록 PL 함수는 기울기가 바뀌는 점들(꺾임점) 만으로 완전히 결정된다. 슬로프 트릭은 이 꺾임점들을 우선순위 큐로 관리한다.

표현

볼록 PL 함수 $$f$$ 는

최솟값 $f_{\min}$ ,
기울기가 1씩 감소하는 왼쪽 꺾임점들의 multiset $$L$$ (최댓값이 top인 max-heap),
기울기가 1씩 증가하는 오른쪽 꺾임점들의 multiset $$R$$ (최솟값이 top인 min-heap)

로 표현한다. $$L$$ 의 최댓값과 $$R$$ 의 최솟값 사이가 최소 구간(기울기 0)이다. 각 꺾임점은 "거기서 기울기가 1 변한다"는 단위 정보로 정규화한다(기울기가 2 변하면 같은 점을 두 번 넣는다).

기본 연산

연산	$$L,R$$ 변화
$f(x) \mathrel{+}= \|x-a\|$	$$a$$ 를 $$L,R$$ 양쪽에 넣고, 교차하면 교환하며 $f_{\min}$ 보정
$f(x)\mathrel{+}= \max(0, x-a)$	$$a$$ 를 $$R$$ 에 (오른쪽만 기울기 증가)
$f(x)\mathrel{+}=\max(0, a-x)$	$$a$$ 를 $$L$$ 에
전체 $$x$$ 평행이동 (shift)	heap의 lazy 오프셋
prefix-min ( $g(x)=\min_{y\le x}f(y)$ )	$$R$$ 비움 (오른쪽 상승 제거)

$$|x-a|$$ 추가의 정확성

$|x-a| = \max(0,a-x)+\max(0,x-a)$ 이므로 왼·오른쪽에 각각 $$a$$ 를 넣는다. 그런데 두 힙의 최댓값/최솟값 순서가 어긋나면(즉 $$a$$ 가 현재 최소 구간을 벗어나면) 두 top을 교환하고 그 차이만큼 $f_{\min}$ 이 증가한다. 이 보정이 슬로프 트릭의 핵심 한 줄이다.

복잡도

각 단계가 힙 연산 $O(\log n)$ , 단계가 $$n$$ 개면 전체 $O(n\log n)$ . 함수 전체를 $$O(n)$$ 으로 들고 갱신하던 것을 꺾임점만으로 압축한 결과다.

2강 슬로프 트릭 구현과 응용 공식

대표 문제: 비감소 수열로 만드는 최소 비용

수열 $$a_i$$ 를 비감소로 만들 때 $\sum |a_i - b_i|$ 최소( $$b$$ 가 비감소). $$f_i(x)$$ = " $$b_i=x$$ 일 때까지의 최소비용", 비감소 제약은 $f_i \leftarrow \text{prefixMin}(f_{i-1}) + |x-a_i|$ .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll min_cost_nondecreasing(vector<int>& a) {
    priority_queue<ll> L;    // 왼쪽 꺾임점들 (max-heap)
    ll cost = 0;             // f_min 누적
    for (int x : a) {
        L.push(x);           // |x - a_i| 의 왼쪽 후보
        if (L.top() > x) {   // a_i 가 현재 최소 구간보다 왼쪽이면 보정
            cost += L.top() - x;
            L.pop();
            L.push(x);       // 오른쪽 top을 왼쪽으로 끌어옴(여기선 단일 힙 트릭)
        }
    }
    return cost;
}

위는 "비감소"에 특화된 단일 힙 축약형이다. 양쪽 힙을 쓰는 일반형은 다음과 같다.

struct SlopeTrick {
    priority_queue<ll> L;                              // max-heap
    priority_queue<ll, vector<ll>, greater<ll>> R;     // min-heap
    ll addL = 0, addR = 0, minf = 0;                   // lazy shift, 최솟값

    void add_abs(ll a) {                               // f += |x - a|
        L.push(a - addL); R.push(a - addR);
        if (L.top() + addL > R.top() + addR) {         // 교차 보정
            ll l = L.top() + addL, r = R.top() + addR;
            L.pop(); R.pop();
            L.push(r - addL); R.push(l - addR);
            minf += l - r;
        }
    }
    void add_inc(ll a) { R.push(a - addR);             // f += max(0, x - a)
        if (R.top() + addR < L.top() + addL) { /* 보정 동일 */ } }
    void shift(ll dl, ll dr) { addL += dl; addR += dr; } // 구간 이동
    void prefix_min() { while(!R.empty()) R.pop(); }     // 오른쪽 상승 제거
};

자주 하는 실수

단위 정규화. 기울기가 한 점에서 2 이상 꺾이면 그만큼 중복 push해야 한다.
교차 보정 빠뜨림. add_abs 에서 $L_{top} > R_{top}$ 일 때 교환 + minf 보정을 꼭 한다. 빼면 비볼록이 되어 틀린다.
lazy shift 부호. 힙에는 오프셋을 뺀 값을 저장하고 꺼낼 때 더한다. 부호 일관성이 핵심.
prefix-min 방향. "이후 자유롭게 키울 수 있다" 의미면 오른쪽 힙을 비운다. 반대 방향 제약이면 왼쪽을 비운다.

응용

문제	변환
비감소/단조 수열로 만들기	prefix-min + $$\|x-a\|$$
막대 정렬·자리 옮기기 최소비용	절댓값 비용 누적
창고/생산 평탄화	구간 이동 + 절댓값
트리 위 볼록 DP 병합	small-to-large 힙 병합

트리로의 확장

자식들의 슬로프 트릭 힙을 부모로 병합할 때 작은 힙을 큰 힙에 합치면(small-to-large) 트리 전체가 $O(n\log^2 n)$ . 볼록성이 보존되므로 병합 후에도 같은 연산을 쓸 수 있다.

연산	$\(L,R\)$ 변화
$f(x) \mathrel{+}= \|x-a\|$	$\(a\)$ 를 $\(L,R\)$ 양쪽에 넣고, 교차하면 교환하며 $f_{\min}$ 보정
$f(x)\mathrel{+}= \max(0, x-a)$	$\(a\)$ 를 $\(R\)$ 에 (오른쪽만 기울기 증가)
$f(x)\mathrel{+}=\max(0, a-x)$	$\(a\)$ 를 $\(L\)$ 에
전체 $\(x\)$ 평행이동 (shift)	heap의 lazy 오프셋
prefix-min ( $g(x)=\min_{y\le x}f(y)$ )	$\(R\)$ 비움 (오른쪽 상승 제거)