1 问题
李超线段树是线段树的一种变种，主要用于维护二维平面上的直线信息以及查询操作。它的应用范围很广，只要式子的形式能转化为一次函数就可以考虑使用李超线段树进行求解 / 优化。
具体的，李超线段树支持下面两种操作：
- 动态在平面中插入一条线段 / 直线。
- 在平面上询问与一条直线 \(x=k\) 相交的线段 / 直线中，交点纵坐标最大点的坐标 / 编号。
2 过程
李超线段树的实质是在 \(x\) 轴上对单位长度维护线段树，而在线段树上的每一个节点，维护一个该区间的最优线段，其定义如下：
- 该线段定义域覆盖整个区间。
- 该线段在区间中点处取值最大。
那么考虑怎样插入的时候维护这个最优线段。设当前遍历到区间 \([l,r]\)，原区间最优线段为 \(l_1\)，当前要插入 \(l_2\)。
- 若当前区间无最优线段，或 \(l_2\) 完全在 \(l_1\) 上方，将 \([l,r]\) 的最优线段改为 \(l_2\)。
- 若 \(l_1\) 完全在 \(l_2\) 上方，则 \([l,r]\) 最优线段不变。
- 否则，比较二者在 \(mid\) 处的大小，然后向下递归：
- 此时考虑上面不是最优线段的线段 \(l\)，它仍可能成为接下来子区间的最优线段。我们现在需要知道这条线段 \(l\) 和另一条线段在哪个区间相交，就向哪个区间递归。
- 具体的，我们比较两个线段在两个端点的大小情况，然后以此判断交点位置即可。如果 \(l\) 在左端点处取值更小，又因为 \(l\) 在终点处取值也更小，因此交点必在右区间；否则就应该在左区间。
对于查询，由于我们维护的是每一个区间在 \(mid\) 处取最大值的线段，那么实际上每一个节点维护的信息是类似于没有下传的懒标记的。所以查询时，我们要从查询点对应的叶子节点一路向上走并取最大值。这实际上是标记永久化的思想。
如果插入的是线段，那么单次查询复杂度为 \(O(\log n)\)，而单次插入复杂度为 \(O(\log^2 n)\)。如果插入的是直线，查询复杂度不变，单次插入复杂度变为 \(O(\log n)\)。
同时值得注意的是，由于李超线段树常常维护的是值域上的信息，因此会需要用动态开点，而李超线段树动态开点的空间复杂度是 \(O(m)\) 的，其中 \(m\) 为线段个数。
3 实现
（下列代码以动态开点形式实现）
对于插入直线的查询操作：
void mdf(int &p, int l, int r, Seg g) {
if(!p) {//该区间没有最优线段
p = ++tot;
t[p].s = g;//直接更新
return ;
}
int mid = (l + r) >> 1;
if(g.calc(mid) > t[p].s.calc(mid)) swap(g, t[p].s);
//比较终点处的值，让 t[p].s 中存的是最优线段
if(l == r) {//递归到叶子节点了
return ;
}
if(t[p].s.calc(l) > g.calc(l)) mdf(rp, mid + 1, r, g);
//如果左端点最优线段取值更大，则说明交点在右端点
else if(t[p].s.calc(l) < g.calc(l)) mdf(lp, l, mid, g);
//否则在左端点
}
对于插入线段的操作，先 \(O(\log n)\) 的将线段拆成几段，然后对于每一段再用与上面方法相同的插入方式处理即可。这也解释了为什么插入线段复杂度为 \(O(\log^2 n)\)。
对于查询 \(x=k\) 直线交点最大值：
int query(int p, int l, int r, int x) {
if(!p) return -Inf;
if(l == r) {
return t[p].s.calc(x);
}
int mid = (l + r) >> 1;
if(x <= mid) return max(t[p].s.calc(x), query(lp, l, mid, x));
else return max(t[p].s.calc(x), query(rp, mid + 1, r, x));//标记永久化的处理方式
}
整体代码实现：
struct Seg {//封装直线
int k, b;
int calc(int x) {
return k * x + b;
}
};
int rt;
struct LC_SegTree {//封装李超线段树
struct node {
int l, r;
Seg s;
}t[Maxn];
#define lp t[p].l
#define rp t[p].r
int tot;
void mdf(int &p, int l, int r, Seg g) {
if(!p) {
p = ++tot;
t[p].s = g;
return ;
}
int mid = (l + r) >> 1;
if(g.calc(mid) > t[p].s.calc(mid)) swap(g, t[p].s);
if(l == r) {
return ;
}
if(t[p].s.calc(l) > g.calc(l)) mdf(rp, mid + 1, r, g);
else if(t[p].s.calc(l) < g.calc(l)) mdf(lp, l, mid, g);
}
int query(int p, int l, int r, int x) {
if(!p) return -Inf;
if(l == r) {
return t[p].s.calc(x);
}
int mid = (l + r) >> 1;
if(x <= mid) return max(t[p].s.calc(x), query(lp, l, mid, x));
else return max(t[p].s.calc(x), query(rp, mid + 1, r, x));
}
}seg;