维护由若干点(x, y)构成上凸包，并支持求给定一个斜率k的求通过某个点截距的最大值， 需保证 x 递增，

询问 k 递减是用query，否则用query2, 单次log(n)， 判断需要用到叉积， 注意是否会爆掉LL。

namespace CH {

struct Point {
    LL x, y;
    Point(LL x = 0, LL y = 0) : x(x), y(y) {}
    Point operator - (const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
};


inline LL Det(Point A, Point B) {
    return A.x * B.y - B.x * A.y;
}

struct ConvexHull {
    Point P[N];
    int be, ed;
    void init() {
        be = 1, ed = 0;
    }
    void add(LL x, LL y) {
        Point cur(x, y);
        while(be < ed && Det(cur - P[ed], P[ed] - P[ed - 1]) <= 0) ed--;
        P[++ed] = Point(x, y);
    }
    LL query(LL k) {
        Point cur(1, k);
        while(be < ed && Det(cur, P[be + 1] - P[be]) >= 0) be++;
        return P[be].y - k * P[be].x;
    }
    LL query2(LL k) {
        Point cur(1, k);
        int low = be + 1, high = ed, mid, pos = be;
        while(low <= high) {
            mid = low + high >> 1;
            if(Det(cur, P[mid] - P[mid - 1]) >= 0) pos = mid, low = mid + 1;
            else high = mid - 1;
        }
        return P[pos].y - k * P[pos].x;
    }
};

}

View Code

 

 

维护由若干直线(y = k * x + m) 构成的下凸包，并支持给定一个 x 坐标， 求所有直线的 y 的最大值， 

没有用到叉积所以答案不怎么会爆LL。

namespace LC {
/**
 * Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
 * Time: O(log N)
 */
 
struct Line {
    mutable LL k, m, p;
    bool operator < (const Line& o) const { return k < o.k; }
    bool operator < (LL x) const { return p < x; }
};
 
struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const LL inf = LLONG_MAX;
    LL div(LL a, LL b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(LL k, LL m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    LL query(LL x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};
}

View Code