Hello Codeforces, I've been trying to learn how to run a DP with the convexhull optimization and I have seen this code for a line container (KTH pdf):
struct Line {
mutable long long k, m, p;
bool operator<(const Line& o) const {
return Q ? p < o.p : k < o.k;
}
};
struct LineContainer : multiset<Line> {..}
So depending in the value of Q the comparator function will do different things, how does multiset cope with this? and how does it affect the complexity of this container?
Thank you very much for the help!
It will behave as Q were constant and it'll assume the operator defines a partial order on the data you are using on your set. If you change the value of Q and this change mess up the current order relations the multiset "will not be aware" of this change and will probably miss behave.
It has happened to me that once I used a inconsistent order on a sort and got a infinite loop. It was probably trying to sort something like this:
A > B
B > C
C > Anl
In other cases, I think the complexity should remain the same because the tree height should still be O(log n).
yeah, it seems that the order will become undefined when the comparator changes, Thank you!