核心概述：维护形如 kx+m 的直线集合并在给定 x 上查询最大值（Convex Hull Trick 变体），支持动态插入与在线查询，时间 O(log N)。
原文引述：
Description: Container where you can add lines of the form kx+m, and query maximum values at points x. Useful for dynamic programming (“convex hull trick”). Time: O(\log N) (for doubles, use inf = 1/.0, div(a,b) = a/b)
展开阐述：
- 定义与问题背景、适用场景
- 面向形如 f(x)=kx+m 的线性函数族，支持在任意 x 上查询 max_k (k x + m)。
- 典型用于动态规划优化（Convex Hull Trick，Cht），尤其当插入顺序与查询顺序不能保证单调时需要支持一般 O(log N) 的插入/查询。
- 接口与数据结构字段（依据实现）
- Line：mutable ll k, m, p；p 表示该直线相对“下一条直线”的分界 x（交点的向下取整位置），用于二分查找定位最优线。
- LineContainer：继承 multiset<Line, less<>>，按斜率 k 排序；重载 operator<(ll x) 以便将查询值 x 与 p 比较，从而 lower_bound(x) 直接命中最佳直线。
- 核心算法流程/操作说明
- div(a,b)：返回向下取整的整除，a/b - ((a^b)<0 且 a%b≠0)，确保交点 x 坐标在整型域中“楼取整”，维持段的覆盖不相交。
- isect(x,y)：
- 若 y==end()：x→p=inf；
- 若斜率相等：x→p=(x.m > y.m)? inf : -inf（截距小者被彻底支配）；
- 否则：x→p = div(y.m - x.m, x.k - y.k)；返回 x→p ≥ y→p 以判定 y 是否被新线淘汰。
- add(k,m)：
- 插入新线，维护与相邻线的交点分界 p；对被支配的直线进行删除，保证集合中仅保留上凸壳必要直线。
- query(x)：
- 通过 lower_bound(x) 找到 p ≥ x 的直线并返回 k*x + m；要求容器非空。
- 复杂度与边界条件
- 插入与查询均为 O(log N)；删除发生在维护壳体的过程中，均摊仍为对数级。
- 当需求为“最小值”时，可对 k, m 取相反数实现。
- 浮点版：按注释 inf=1/.0，div 直接用 a/b，注意精度与比较误差。
- 实现细节与易错点
- 斜率排序与 p 的单调性：集合内按 k 排序，p 随 multiset 中顺序单调；确保 isect 后将过时直线移除。
- 整数除法的符号：div 需处理负数向下取整，避免边界错位导致查询段重叠或空洞。
- 可变成员 p：声明为 mutable 以便在 multiset 中更新分界而不破坏键的有序性约束。
- 变体/扩展
- 若插入斜率单调且查询 x 单调，可使用更快的双端队列 CHT 实现；若需二维/凸包相关问题可参考 025-几何-凸包。
- 若需要与分治优化结合，可参考 130-杂项-分治DP。
- 正确性要点与直觉
- 维护上凸壳：集合中任意“中间”且被相邻两线支配的直线会被删除；查询时通过 p 的二分在壳的分段上定位，保证返回段内最优线。