「数据结构」李超线段树

#0.0 屑在前面

李超线段树 由学军中学队爷李超在省选讲课中提出。

事实上，整体来看并没有什么特别特别的，只是线段树维护的信息特殊化了。

#1.0 概述

#1.1 适用问题

支持动态维护一个平面直角坐标系，支持插入直线/线段，查询与直线 \(x=x_0\) 的直线/线段交点纵坐标最大/最小的直线。

#1.2 大致思想

维护每个区间中，完全通过该区间，且位于最上层长度最长的直线，利用标记永久化思想。

考虑插入一条直线，且处理到了某个区间，那么可能有以下几种情况：

• 当前区间没有被任何一条线段覆盖，直接修改；
• 根据端点值判断新的线段是否完全被原本线段覆盖，直接返回；
• 根据端点值判断新的线段是否完全覆盖原本线段，直接修改，然后返回；
• 通过交点位置与端点值的大小关系判断长度关系，将长的记录，短的递归进入相应子树；

查询时就是标记永久化的思想，将所经过的每一条被记录的线段都拿出来比较即可。

综上，查询的时间复杂度是 \(O(\log n)\).

事实上，对于要插入的线段，我们先将其能覆盖的区间通过线段树划分为 \(O(\log n)\) 个，每个完全覆盖的区间再单独进行上面的操作，上面单独操作时，每次线段长度至少减半，于是最多向下递归 \(O(\log n)\) 层，于是修改总体时间复杂度为 \(O(\log^2n)\).

#2.0 应用

#2.1 板子

P4254 [JSOI2008]Blue Mary开公司

由于插入的是直线而不是线段，于是不需要先分段，可以直接进行修改。

#define ll long long
#define db double

const int N = 200010;
const int LMT = 50010;
const int INF = 0x3fffffff;

template <typename T> void read(T &x) {
    int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T x, T y) {return x > y ? x : y;}
template <typename T> inline T Min(T x, T y) {return x < y ? x : y;}

struct Node {int ls, rs, val;};
struct Line {
    double k, b;
    inline Line() {k = b = 0;}
    inline Line(double _k, double _b) {k = _k, b = _b;}
    inline double val(int x) {return k * x + b;}
} s[N];

struct LCTree {
    Node p[N]; int cnt, rt;

    inline LCTree() {cnt = rt = 0;}

    void build(int &k, int l, int r) {
        if (!k) k = ++ cnt; if (l == r) return;
        int mid = l + r >> 1; p[k].val = 0;
        build(p[k].ls, l, mid); build(p[k].rs, mid + 1, r);
    }   

    void insert(int k, int l, int r, int id) {
        if (!p[k].val) {p[k].val = id; return;}
        int mid = l + r >> 1;
        db l2 = s[p[k].val].val(l), r2 = s[p[k].val].val(r);
        db l1 = s[id].val(l), r1 = s[id].val(r);
        if (l1 <= l2 && r1 <= r2) return;
        if (l1 > l2 && r1 > r2) {p[k].val = id; return;}
        db x = (s[id].b - s[p[k].val].b) / (s[p[k].val].k - s[id].k);
        if (l1 > l2) {
            if (x > mid) insert(p[k].rs, mid + 1, r, p[k].val), p[k].val = id;
            else insert(p[k].ls, l, mid, id);
        } else {
            if (x > mid) insert(p[k].rs, mid + 1, r, id);
            else insert(p[k].ls, l, mid, p[k].val), p[k].val = id;
        }
    } 
    
    double query(int k, int l, int r, int x) {
        if (l == r) return s[p[k].val].val(x);
        int mid = l + r >> 1; double res = s[p[k].val].val(x);
        if (x <= mid) return Max(query(p[k].ls, l, mid, x), res);
        else return Max(query(p[k].rs, mid + 1, r, x), res);
    }
} t;

int n, lcnt, T; char op[N];

inline void Main() {
    scanf("%s", op);
    if (op[0] == 'P') {
        double k = 0, b = 0; scanf("%lf%lf", &b, &k);
        s[++ lcnt] = Line(k, b - k); t.insert(t.rt, 1, LMT, lcnt);
    } else {
        int x = 0; read(x);
        printf("%lld\n", (ll)(t.query(t.rt, 1, LMT, x) / 100.0));
    }
}

int main() {t.build(t.rt, 1, LMT); read(T); while (T --) Main(); return 0;}

#2.2 斜率优化

「NOI2007」货币兑换

设 \(f_i\) 表示到第 \(i\) 天可以拥有的最大钱数，先写出一个大概的转移方程 \[ f_i=\max\limits_{0<j<i}\{num_A\cdot a_i+num_B\cdot b_i\}, \] 其中 \(num_A\) 与 \(num_B\) 分别表示持有的 \(A\) 金卷的数量与 \(B\) 金卷的数量，这两个数由 \(j\) 决定。显然，第 \(j\) 天买入时，能得到的金卷比例是一定的，于是当天买入时拥有的钱数越大越好，也就是 \(f_j\)，应当有 \[ \begin{aligned} f_j&=num_A\cdot a_j+num_B\cdot b_j\\ f_j&=num_B\cdot R_j\cdot a_j+num_B\cdot b_j\\ num_B&=\dfrac{f_j}{R_j\cdot a_j+b_j}, \end{aligned} \] 同理可得 \[ num_A=\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}, \] 于是我们可以写出完整的状态转移方程 \[ f_i=\max\limits_{0<j<i}\left\{\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}\cdot a_i+\dfrac{f_j}{R_j\cdot a_j+b_j}\cdot b_i\right\},\\ \frac{f_i}{b_i}=\max\limits_{0<j<i}\left\{\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}\cdot \frac{a_i}{b_i}+\dfrac{f_j}{R_j\cdot a_j+b_j}\right\}, \] 于是我们就可以直接将一个决策看作一条斜率为 \(\frac{f_j\cdot R_j}{R_j\cdot a_j+b_j}\)、纵轴截距为 \(\frac{f_j}{R_j\cdot a_j+b_j}\) 的直线，对于 \(i\)，我们要求的就是已有的所有决策直线与 \(x=\frac{a_i}{b_i}\) 交点纵坐标的最大值。于是就可以直接用李超线段树进行维护。

参考文章

• [1] 李超线段树 - 小蒟蒻yyb

• [2] 李超线段树 - OI Wiki