Li Chao Min

//we assume here n = 1e6, use limits appropriate to the problem
struct Line //mx + b
{
    ll m;
    ll b;
    ld f(ld x)
    {
        return m*x + b;
    }
};

ll f(Line L, ll x)
{
    return L.m*x + L.b;
}

Line tr[4000000];
struct CHT_MIN //lichao tree
{
    void build(int lo = 1, int hi = 1e6+1, int cur = 1)
    {
        if (tr[cur].m == 0 && tr[cur].b == INF) return;
        tr[cur] = {0, INF};
        if (hi-lo == 1) return;
        int mid = (lo+hi)/2;
        build(lo, mid, cur*2);
        build(mid, hi, cur*2+1);
    }
    void upd(Line L, int lo = 1, int hi = 1e6+1, int cur = 1)
    {
        int mid = (lo+hi)/2;
        ll optMid = L.f(mid) < tr[cur].f(mid);
        ll optLow = L.f(lo ) < tr[cur].f(lo );
        if (optMid) swap(L, tr[cur]);
        if (hi-lo == 1) return;
        if (optMid != optLow) upd(L, lo, mid, cur*2);
        else upd(L, mid, hi, cur*2+1);
    }
    ll get(int x, int lo = 1, int hi = 1e6+1, int cur = 1)
    {
        int mid = (lo+hi)/2;
        ll val = f(tr[cur], x);
        if (hi-lo == 1) return val;
        if (x < mid) return min(val, get(x, lo, mid, cur*2));
        else return min(val, get(x, mid, hi, cur*2+1));
    }
};