李超树

· · 个人记录

李超树能解决的问题是：

给一堆直线（y = kx + b,用(k, b)来表示),并且一边给，一边问x = pos的最大的 y 的值。

做法

维护一个线段树，每个节点维护一条当前区间内的优势直线，即从上往下看最长的直线 （其实是mid处最高的点所在直线）， 且每条直线最多只被一个节点维护。

要大力分类讨论（该点是否曾有直线，直线是否有交，哪条直线的上面部分更长）。注意 如果当前直线胜选，就要把原有直线扔下去，因为原有直线在下面的某些点可能更有优势。

查询：从 根 到 代表该 pos 的叶子 的所有节点 所代表的直线在 pos 的 y 值的最大值。

$l_{cur}/r_{cur}$ : 正插入直线的左右端点。 模板提交处： [P4254 [JSOI2008]Blue Mary开公司](https://www.luogu.com.cn/problem/P4254) (记得一开始要 ```b -= k```） ## 李超树加强版：[“线段”版李超树](https://www.luogu.com.cn/problem/P4097)： 然而最常见的还是“线段”版李超树，即给线段的左右端点，单点查询。把线段拆成许多完整覆盖线段树节点的小线段，然后再做。 例题中要求最优线段编号（这同样也是常见的应用时的情况）。因此有如下代码，更加简便些：（提示：对 $mem$ 的修改就相当于对 $id[cur]$ 的修改。）（按斜率排序是个好东西） ```cpp //毕竟每个节点存的是中间点的最高点，因此就直接比较两线段的中间点即可。 void insert(int L, int R, int nwid, int &cur) void modify(int L, int R, int l, int r, int nwid, int &cur) { if (!cur) cur = ++ttot; if (l <= L && R <= r) { insert(L, R, nwid, cur); return ; } int mid = (L + R) >> 1; if (l <= mid) modify(L, mid, l, r, nwid, ls[cur]); if (r > mid) modify(mid + 1, R, l, r, nwid, rs[cur]); } ``` ## 李超树二次加强版：[P4069 [SDOI2016]游戏](https://www.luogu.com.cn/problem/P4069)（查最低点） 将 $dis[cur]$ 当作横坐标，将 $cur$ 上数字看作纵坐标，发现**链上的数字与 $dis[cur]$ 成一次函数关系**（当然要拆成两种链）。再加之以树链剖分，操作就变成了一段段的线段（$dfn$ 数组上的），查询就是查询 一段段 区间内的最小值 的最小值。 与上一道题不同，这回成了区间查询，且维护的是离散化后的线段树。 也不难，维护 $mn$ 表示当前节点子树内最高点。然后 $O(n)~ ~->O(logn)$. 至于离散化，不要忘记李超树其实就是在维护个凸包（类似半平面交），只不过由于横坐标只有有限种可能。因此维护**每种横坐标的特殊值**作为L和R的意义。注意，$mid$ 还是 $(L + R) >> 1$，只不过用的是mid的原数值 $(dis[ded[mid]])

注意！！！

从根到叶子的所有线段都要算一下，包括拆成小线段节点之前的大节点，但是这些线段可能没有完全覆盖询问区间，要进行特判！！！！

res = have_segments[cur] ? min(dis[ded[max(l, L)]] * k[cur] + b[cur], dis[ded[min(r, R)]] * k[cur] + b[cur]) : inf;

不知道为什么会出现万分之一的错，不特判就是95WA。哪位大佬知道原因啊？（已经调到心态爆炸）

应用

（暂时鸽掉）

CF932F Escape Through Leaf

CF1303G Sum of Prefix Sums

时间还是不够使，况且线段树等数据结构难调，斜率等计算几何更难调，等我有时间了最好还是多做做，锻炼码力

2020.11.19 Update:

一轮复习学了 zzz 大佬的写法，A 掉了 Escape Through Leaf（李超树合并），并没有上百行。感觉 zzz 大佬的写法好简便啊！现在感觉李超树也没那么难调了。于是删掉了之前的许多代码，毕竟那些太麻烦了。

模板（调试用)

来源:RPG游戏

namespace LCT {
    inline int calc(int x, int id) {
        return b[id] * x + f[id] - (X(id) + Y(id)) * b[id];
    }
    inline bool cmp(int x, int lhs, int rhs) {
        return calc(x, lhs) > calc(x, rhs);
    }
    int ls[NN], rs[NN], bst[NN], ttot;
    void ins(int L, int R, int id, int &cur) {
        if (!cur) {
            cur = ++ttot;
            bst[cur] = id;
            return ;
        }
        bool tl = cmp(L, id, bst[cur]), tr = cmp(R, id, bst[cur]);
        if (tl && tr)   return bst[cur] = id, void();
        if (!tl && !tr) return ;
        int mid = (L + R) >> 1;
        if (cmp(mid, id, bst[cur])) swap(id, bst[cur]), tl = !tl, tr = !tr;
        if (tl) ins(L, mid, id, ls[cur]);
        else    ins(mid + 1, R, id, rs[cur]);
    }
    int query(int L, int R, int x, int cur) {
        if (!cur)   return -inf;
        int res = calc(x, bst[cur]);
        int mid = (L + R) >> 1;
        if (x <= mid)   MAX(res, query(L, mid, x, ls[cur]));
        else    MAX(res, query(mid + 1, R, x, rs[cur]));
        return res;
    }
}