简介
李超线段树是一种能维护一些线段/直线极值的数据结构，具体能维护 \(x = k\) 时所有线段中最大/最小的 \(y\) 值，支持动态插入线段，单点的全局查询。一般可以用于维护不保证斜率单调性的凸包（比如做斜率优化 dp）；在树上问题还能支持线段树合并，具体就是在节点处插入线段，其他的和普通线段树没有区别；如果想要维护区间信息可以用线段树/树状数组+离线做扫描线嵌套，也可以做到 \(\log ^2 n\)。
经典应用：P4097 动态插入线段，查询单点极值
省流：每次插入线段 \(y = kx + b\)，其定义域 \(x \in [l, r]\)；求当前局面下 \(x = k\) 时取到最大 \(y\) 值的线段，若有多条这样的线段，输出最早出现（编号最小的）那一条。
李超线段树自然是线段树的结构，也就是以 \(x\) 轴为下标划分的线段树。那代表区间 \(x \in [l, r]\) 的线段树节点 \(p\) 维护的是什么？设 \(mid = \frac {l + r}{2}\)，\(p\) 维护的就是在 \(mid\) 处取到最大值的线段是哪一条。那怎么维护这个信息呢？我们现在考虑插入一条线段 \(y = kx + b\)，其定义域 \(x \in [l, r]\)，那找出所有被 \([l, r]\) 完全包含的线段树上区间，只有这些区间的中点处最优线段可能会改变，于是我们考虑对这样的一个区间 \(p \rightarrow [l, r]\) 进行更新：（这里我们定义在 \(x\) 处，线段 \(u\) 优于 \(v\) 为 \(u\) 在 \(x\) 的值大于 \(v\) 在 \(x\) 的值，或者这两者值相同但是 \(u\) 编号比 \(v\) 小）
设现在要插入的线段为 \(u\)，原先的最优线段为 \(v\)，&v = tr[p] 是为了方便直接修改 \(tr_p\)。
-
如果 \(u\) 在 \(mid = \frac {l + r}{2}\) 处优于 \(v\)，那么将 \(u, v\) 互换，往下递归。记得这时候如果 \(l = r\) 直接
return ;。 -
考虑 \(p\) 的更改对两个儿子的影响，我们将目前的 \(u\) 在 \(l, r\) 处的取值与 \(v\) 在 \(l, r\) 处的取值比较：
-
如果 \(u\) 在 \(l\) 处优于 \(v\) 在 \(l\) 处，说明 \(u, v\) 在 \([l, mid]\) 肯定有交点，\(u\) 会对左区间的一些节点值产生影响，所以往左儿子递归。
-
如果 \(u\) 在 \(r\) 处优于 \(v\) 在 \(r\) 处，同上。
-
否则 \(u\) 就是无用的线段。
-
那我们怎么定位 \(y = kx + b, x \in [l, r]\) 完全覆盖的区间呢？像线段树一样就好了。对一个区间的插入是 \(\log V\) 的，因为 \(u, v\) 最多一个交点，所以最多往一边递归；每条线段只会完全覆盖 \(\log V\) 个区间。所以全局插入一条线段是 \(\mathcal {O} (\log ^ 2 V)\) 的。
查询怎么做？这里采取标记永久化的思想，查询 \(x = k\) 处的极值，那么从线段树根节点到 \([k, k]\) 的路径上经过的所有节点的最优线段都有可能成为最终答案，进行一个权值 & 编号的比较即可。其余和普通线段树无异。
代码实现有一些小细节：
-
这题要求在 \(y\) 取到最大的基础上最小化线段的标号，所以要专门写一个
pair以及自定义的比较器。 -
因为是浮点数的计算所以类型会转化的运算中要开
double，然后判断大小的时候设一个精度误差 \(eps\)。 -
计算直线斜率的时候如果两端点 \(x_0 = x_1\)，记得设 \(k = 0\)，要不然直接除会除 \(0\) 报错。
-
强制在线模数的问题。首先 \(x,y\) 的模数不同，其次取模后必须是整数，所以采取
+P 再 %P的方式。 -
线段树空间大小：值域的四倍。
贴一下 Code：
#include <bits/stdc++.h>
#define ll long long
#define db double
#define lc (p << 1)
#define rc (p << 1 | 1)
#define pdi pair<db, int>
#define mr make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 5, M = 4e4 + 5, M1 = 39989, M2 = 1e9;
const db eps = 1e-9;
int n, m, lst;
struct Line{
db k, b;
} a[N];
int newline(int x0, int y0, int x1, int y1) {
m++;
if(x0 == x1) a[m].k = 0, a[m].b = max(y0, y1);
else a[m].k = (db)1.0 * (y0 - y1) / (x0 - x1), a[m].b = (db)y0 - (db)a[m].k * x0;
return m;
}
db calc(int u, db x) {
return a[u].k * x + a[u].b;
}
int cmp(db x, db y) {
if(x - y > eps) return 1;
else if(y - x > eps) return -1;
else return 0;
}
namespace LiChaoSegT{
int tr[N << 2];
void upd(int p, int l, int r, int u) {
int &v = tr[p], mid = l + r >> 1;
int bmid = cmp(calc(u, mid), calc(v, mid));
if(bmid == 1 || (!bmid && u < v)) swap(u, v);
if(l == r) return ;
int bl = cmp(calc(u, l), calc(v, l)), br = cmp(calc(u, r), calc(v, r));
if(bl == 1 || (!bl && u < v)) upd(lc, l, mid, u);
if(br == 1 || (!br && u < v)) upd(rc, mid + 1, r, u);
return ;
}
void modify(int p, int l, int r, int u, int x, int y) {
if(x <= l && r <= y) return upd(p, l, r, u), void();
int mid = (l + r) >> 1;
if(x <= mid) modify(lc, l, mid, u, x, y);
if(y > mid) modify(rc, mid + 1, r, u, x, y);
return ;
}
void modify(int u, int x, int y) {
modify(1, 1, M1, u, x, y);
}
pdi pmax(pdi x, pdi y) {
int b = cmp(x.fi, y.fi);
if(b == 1) return x;
else if(b == -1) return y;
return (x.se < y.se ? x : y);
}
pdi query(int p, int l, int r, int x) {
if(x < l || x > r) return {0, 0};
pdi ret = {calc(tr[p], x), tr[p]};
if(l == r) return ret;
int mid = l + r >> 1;
if(x <= mid) return pmax(ret, query(lc, l, mid, x));
else return pmax(ret, query(rc, mid + 1, r, x));
}
int query(int x) {
return query(1, 1, M1, x).se;
}
} using namespace LiChaoSegT;
int main() {
cin >> n;
for (int i = 1, o, x0, x1, y0, y1; i <= n; ++i) {
cin >> o >> x0;
if(o == 0) {
x0 = (x0 + lst - 1 + M1) % M1 + 1;
lst = query(x0); cout << lst << "\n";
}
else {
cin >> y0 >> x1 >> y1;
x0 = (x0 + lst - 1 + M1) % M1 + 1, x1 = (x1 + lst - 1 + M1) % M1 + 1;
y0 = (y0 + lst - 1 + M2) % M2 + 1, y1 = (y1 + lst - 1 + M2) % M2 + 1;
if(x0 > x1) swap(x0, x1), swap(y0, y1);
int u = newline(x0, y0, x1, y1);
modify(u, x0, x1);
}
}
return 0;
}