Freaks City

Li Chao Segment Tree Problem: Maintain a collection S of linear functions with the following operations: Insert a linear function f(x) = kx + b over a range [l, r] Query maxf∈S f(x) for a given x The naive approach decomposes a linear function's range into O(log n) segment tree nodes and stores all functions at each node. However, this can le ...