「HEOI2013」Segment 题解

题目分析

这是一个经典的线段维护问题，需要支持两种操作：

1. 在平面上添加一条线段
2. 查询在某个横坐标 $x = k$ 处，与哪条线段相交的交点纵坐标最大

由于数据规模达到 $10^5$，我们需要一个高效的数据结构来解决这个问题。

算法思路

本题采用 李超线段树 来解决，这是一种专门用于维护线段（直线）并支持区间查询的数据结构。

关键点分析

1. 线段表示：每条线段用斜截式 $y = kx + b$ 表示
2. 垂直线段处理：当 $x_0 = x_1$ 时，线段是垂直的，我们将其视为斜率为 0，截距为两端点纵坐标最大值的水平线段
3. 坐标加密：所有输入坐标都根据上一次查询结果进行加密，需要实时解密

李超线段树实现

struct LiChaoTree {
    struct P {
        int l, r, s;  // 区间左右端点，当前区间的最优线段编号
    } tree[N << 2];
    
    // 构建线段树
    void build(int p, int l, int r) {
        tree[p].l = l, tree[p].r = r;
        tree[p].s = 0;  // 0表示没有线段
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
    }
    
    // 在节点p中尝试插入新线段x
    void update(int p, int x) {
        int y = tree[p].s;  // 当前节点的最优线段
        int mid = (tree[p].l + tree[p].r) >> 1;
        
        // 比较新线段和当前线段在mid处的值
        int t = cmp(calc(x, mid), calc(y, mid));
        
        // 如果新线段更优，则替换
        if (t == 1 || (t == 0 && x < y)) {
            tree[p].s = x;
            swap(x, y);
        }
        
        // 根据在左右端点的比较结果，决定往哪个子树递归
        int tl = cmp(calc(x, tree[p].l), calc(y, tree[p].l));
        int tr = cmp(calc(x, tree[p].r), calc(y, tree[p].r));
        
        if (tl == 1 || (tl == 0 && x < y))
            update(p << 1, x);
        if (tr == 1 || (tr == 0 && x < y))
            update(p << 1 | 1, x);
    }
    
    // 在区间[l, r]上插入线段x
    void change(int p, int l, int r, int x) {
        if (l <= tree[p].l && tree[p].r <= r) {
            update(p, x);
            return;
        }
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (l <= mid) change(p << 1, l, r, x);
        if (mid + 1 <= r) change(p << 1 | 1, l, r, x);
    }
    
    // 查询位置x处的最优线段
    pdi ask(int p, int x) {
        pdi t = make_pair(calc(tree[p].s, x), tree[p].s);
        if (tree[p].l == tree[p].r) return t;
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (x <= mid)
            t = pmax(t, ask(p << 1, x));
        else
            t = pmax(t, ask(p << 1 | 1, x));
        return t;
    }
};

核心函数说明

1. calc(x, t)：计算编号为x的线段在位置t处的纵坐标值
2. cmp(x, y)：浮点数比较，考虑精度误差
3. pmax(x, y)：比较两个结果，优先选择纵坐标更大的，纵坐标相同时选择编号更小的
4. update(p, x)：在节点p中尝试用线段x更新最优线段
5. change(p, l, r, x)：在区间[l, r]上插入线段x
6. ask(p, x)：查询位置x处的最优线段

时间复杂度

• 插入操作：每次插入需要 $O(\log^2 M)$ 时间，其中 $M = 40000$ 是横坐标范围
• 查询操作：每次查询需要 $O(\log M)$ 时间
• 总复杂度：$O(n \log^2 M)$，可以应对 $n = 10^5$ 的数据规模

空间复杂度

使用线段树结构，空间复杂度为 $O(M)$，在本题限制内完全可以接受。

使用技巧

1. 浮点数精度处理：使用 eps 来处理浮点数比较的精度问题
2. 坐标解密：在输入时实时根据 lastans 解密坐标
3. 线段标准化：确保线段的左端点横坐标不大于右端点横坐标
4. 垂直线段特殊处理：将其视为特殊的水平线段

这种解法充分利用了李超线段树的特性，能够高效处理线段插入和查询操作，是解决此类问题的标准方法。