Skip to content

Slope trick

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
template <class T = int>
struct SlopeTrick {

    SlopeTrick(T inf) : inf(inf) {
        ql.push(-inf);
        qr.push(inf);
    }

    void add_slope_l(T a) {
        // add f(x) = max(0, a-x)
        T r0 = qr.top();
        m += std::max(T(0), a - r0);

        a -= num_shift;
        qr.push(a);
        T b = qr.top();
        qr.pop();
        ql.push(b);
    }

    void add_slope_r(T a) {
        // add f(x) = max(0, x-a)
        T l0 = ql.top();
        m += std::max(T(0), l0 - a);

        a -= num_shift;
        ql.push(a);
        T b = ql.top();
        ql.pop();
        qr.push(b);
    }

    void add_const(T a) {
        // add f(x) = a
        m += a;
    }

    void shift(T a) {
        // f(x) <- f(x-a)
        num_shift += a;
    }

    void cummin_l() {
        // f(x) <- min_{y <= x} f(y)
        while (qr.size() > 1) {
            qr.pop();
        }
    }

    void cummin_r() {
        // f(x) <- min_{x <= y} f(y)
        while (ql.size() > 1) {
            ql.pop();
        }
    }

    T min() {
        // min f(x)
        return m;
    }

    T argmin() {
        // argmin f(x)
        T a = ql.top();
        if (a != -inf)
            a += num_shift;
        return a;
    }

  private:
    std::priority_queue<T, std::vector<T>, std::greater<T>> qr;
    std::priority_queue<T> ql;
    T m = 0, num_shift = 0, inf;
};

Example

Reference