题目分析

我们需要维护多条线段，支持两种操作：

1. 插入一条新的线段
2. 查询在某个x坐标处，所有线段中的最高点的y坐标

这是一个典型的动态线段集最值查询问题。

算法思路

关键观察

对于每条线段，我们可以用直线方程 $y = kx + b$ 来表示：

• 斜率 $k = \frac{y_2 - y_1}{x_2 - x_1}$
• 截距 $b = y_1 - k \cdot x_1$

在查询点 $x_0$ 处，线段的y值为：$y = k \cdot x_0 + b$

核心算法：李超线段树

李超线段树是解决此类问题的标准方法：

数据结构设计：

• 线段树维护区间 $[0, 10^5]$（根据数据范围）
• 每个节点存储在该区间内可能成为最大值的线段

操作实现：

1. 插入线段：

   • 从根节点开始，比较新线段与当前节点线段
   • 在中点处比较y值，决定替换策略
   • 递归更新左右子树

2. 查询操作：

   • 从根节点到叶子节点路径上
   • 比较所有经过节点的线段在 $x_0$ 处的y值
   • 取最大值作为答案

复杂度分析

• 插入：$O(\log^2 M)$，其中 $M$ 是x坐标范围
• 查询：$O(\log M)$
• 总体复杂度：$O(m \log^2 M)$，可以处理 $m = 150000$ 的数据规模

代码框架

#include <bits/stdc++.h>
using namespace std;

const int N = 100000;  // x坐标范围
const double eps = 1e-8;

struct Line {
    double k, b;
    Line() : k(0), b(0) {}
    Line(double _k, double _b) : k(_k), b(_b) {}
    double calc(int x) const { return k * x + b; }
};

class LiChaoTree {
private:
    Line tree[N << 2];
    
    void update(int node, int l, int r, Line line) {
        // 李超树插入逻辑
    }
    
    double query(int node, int l, int r, int x) {
        // 查询x处的最大值
    }

public:
    void insert(double k, double b) {
        update(1, 0, N, Line(k, b));
    }
    
    double query(int x) {
        return query(1, 0, N, x);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    LiChaoTree lct;
    
    // 处理初始线段和操作
    // ...
    
    return 0;
}

注意事项

1. 精度问题：使用double类型，注意比较时的精度误差
2. 垂直线段：需要特判 $x_1 = x_2$ 的情况
3. 空查询：没有线段时输出0

总结

本题是李超线段树的模板题，关键在于理解线段树节点存储的是区间内的优势线段，通过递归比较和替换来维护这个性质。掌握此数据结构可以解决一类动态维护函数最值的问题。