... misunderstanding going on forever ...

Thanks for pointing out, I've changed the title of this post as "C++ STL".

Actually, you could get much shorter code if your structure were to inherit from multiset<Line> :) Then instead of e.g. begin(lines) you have begin(), instead of lines.insert(...) you have just insert(...), and you can use iterator as a type (instead of the typedef-ed It). You also have empty() automatically :)

Otherwise it's a neat implementation, I like it. Although instead of succ I prefer to have a double xLeft which is the x-coordinate of the intersection with the previous line in the set. It is easy to binary-search on in eval.

That was brilliant @niklasb , I can understand the algorithm for Dynamic variant of the trick, but i have never seen such usage of STL.

I have a few doubts regarding C++ usage (I am only asking because i could not find much on google). 1. How does this work in language** auto y = insert({ m, b });** line 25 2. what is the name or the idea behind , this mutable function<const Line*()> succ; in Line 4 ? 3. How does the ** bool operator<(const Line& rhs) const** work ?

These questions might sound really dumb,but i just need a stack-overflow link to the name of these ideas i will learn them myself..

After some time with the code I think it has a problem. When a new line is inserted, the function succ must be updated for the new line after all the erases. Also, the succ of the new line's previous should be updated as well.

my suggestion for fixing this issue:

const ll is_query = -(1LL<<62);
struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m < rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m && y->b <= x->b;
        return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
    }
    void insert_line(ll m, ll b) {
        auto y = insert({ m, b });
        ********removed line******
        if (bad(y)) { erase(y); return; }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        while (y != begin() && bad(prev(y))) erase(prev(y));*****added line*****
        **if(y != begin()) prev(y)->succ = [=] { return &*y; };*****added line*****
    }
    ll eval(ll x) {
        auto l = *lower_bound((Line) { x, is_query });
        return l.m * x + l.b;
    }
};

Thank you very much, but as mentioned above this implementation has some issues and bugs. For those wondering, here is the better version of Convex Hull Trick online.

one suggestion. rather than using map<int,vi> path u can use vi path[MAX]. this will reduce ur time complexity by a factor of , and the rest of the code can remain exactly the same.

PS: note that this will not work if u want to access large indices like path[1<<30]. in that case u will have to use map only.