Hello codeforces!
I am trying to learn the Li Chao tree, but there is a part i am unable to understand. All the resources that i found (e.g: cp-algo) describe it by using two lines. With two lines, it makes sense, because one of them will dominate at most one of the two halves, and in this way, we would have to update only one half (similar to segment trees). Although, that is not always the case when there are more lines. I will describe what i mean with an example (check the image below). Let's say, that the blue lines were inserted before, and now we want to insert the red line. In our case, the red line dominates the green highlighted segment that is on both the left and right part of the total range. In the implementation that the sites provide, we always choose to move to one side and thus maintain logarithmic time. But in the case i describe, we should update both the left and the right part.
What am i missing?
Thanks!