<总结>李超线段树

线段树NB

李超线段树:维护最优势直线(选定x的时候y最大/最小的线段)

下面我们维护最大值

开一棵x范围的线段树,然后线段树的每个节点记录这个区间中点最高的线段(x = \frac {(l + r)} 2)

维护时考虑这些情况:

1. 这条线段从高处完全覆盖当前区间的线段: 那原来的线段肯定不会成为答案, 直接替换结束即可
2. 这条线段被当前区间的线段从高处完全覆盖: 那这条线段肯定不会成为答案, 结束

上面两种讨论完不满足就说明新旧两条直线在这个区间的范围内相交(又绿又细的是老直线,又蓝又粗的是新直线,黑色的是区间中点对应的x):

1. 老直线斜率小于新直线斜率, 老直线中点取值小于新直线中点取值

新直线代替这个区间的直线,老直线可能会在左边的子区间发光发热替代其他线段
2. 老直线斜率大于新直线斜率, 老直线中点取值小于新直线中点取值

新直线代替这个区间的直线,老直线可能会在右边的子区间发光发热替代其他线段
3. 老直线斜率小于新直线斜率, 老直线中点取值大于新直线中点取值

新直线可能替代右边区间的直线,递归右边区间
4. 老直线斜率大于新直线斜率, 老直线中点取值大于新直线中点取值

新直线可能替代左边区间的直线,递归左边区间

查询的时候查询覆盖了查询点的log个区间,取最大值即可

struct Line
{
    double a, b;  // y = ax + b

    inline double operator()(int x) { return a * x + b; }
} nd[N << 2];

inline void add(Line X)
{
#define P (nd[p])
#define L (p << 1)
#define R (L | 1)
    int l = 1, r = N, p = 1;
    while (true)
    {
        double o_l = P(l), o_r = P(r), n_l = X(l), n_r = X(r);
        if (n_l <= o_l && n_r <= o_r) return;
        if (n_l >= o_l && n_r >= o_r)
        {
            P = X;
            return;
        }
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (P(mid) < X(mid))
        {
            if (P.a < X.a)
                std::swap(P, X), r = mid, p = L;
            else
                std::swap(P, X), l = mid + 1, p = R;
        }
        else
        {
            if (P.a < X.a)
                l = mid + 1, p = R;
            else
                r = mid, p = L;
        }
    }
}

inline double query(int x)
{
    int    l = 1, r = N, p = 1;
    double ans = 0;
    while (true)
    {
        ans = std::max(ans, P(x));
        if (l == r)
        return ans;
        int mid = (l + r) >> 1;
        if (x <= mid)
            p = L, r = mid;
        else
            p = R, l = mid + 1;
    }
}