李超线段树
定义
可以看看洛谷的模板题目：
作用
- 优化动态规划，如果可以将一个动态规划的转移式子转化为 \(y = kx + b\) 的形式，那么我们可以边转移边将 \(y = kx + b\) 这条线段放入李超线段树，然后在下次转移时，直接调用下次计算出来的 \(x\) 位置上的最大值或最小值。（结合题目理解）
构建方式
以洛谷模板题为例。
插入线段
对于线段树上的区间 \([l, r]\)，保存一个线段编号，定义 \(p(x)\) 表示线段 \(p\) 在横坐标为 \(x\) 时的纵坐标。
当有新的线段来时，以以下方式更新。
- 取区间 \([l, r]\) 的中点 \(mid\)。
- 看看将 \(mid\) 作为横坐标时，保存的线段 \(id\) 和新来的线段 \(seg\) 谁大，如果 \(seg(mid)\) 比 \(id(mid)\) 大，那么交换 \(id\) 和 \(seg\)，这时 \(id(mid) < seg(mid)\)。
- 接下来我们看看 \(id\) 这条线段是否还有可能成为左右区间的代表线段，看看做左端点谁大，如果 \(id(l)\) 比 \(seg(l)\) 更大，那么递归更新区间 \([l, mid]\)，线段为 \(id\)。
- 然后再看看右区间，如果 \(id(r)\) 比 \(seg(r)\) 更大，那么递归更新区间 \([mid + 1, r]\)，线段为 \(id\)。
因为 3. 4 中的条件只有一种可能实现，这也说明了：
- 只有一种情况会往下递归;
- 不能用 pushdown;
- 时间复杂度为 \(O(\log^2 n)\)。
查询线段
我们可以按照线段树区间查询的顺序，从上往下按照取出的线段，比较其在横坐标为 \(x\) 的大小。
模板代码
P4097
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const double eps = 1e-6;
int cmp(double x, double y) {
if (fabs(x - y) < eps) return 0;
if (x < y) return -1;
return 1;
}
struct node {
int id;
} tr[N << 2];
double gety(double k, int x, double b) {
return k * x + b;
}
double k[N], b[N];
bool compare(int v1, int v2, int x) {
double y1 = gety(k[v1], x, b[v1]);
double y2 = gety(k[v2], x, b[v2]);
if (!cmp(y1, y2)) return v1 < v2;
return cmp(y1, y2) == 1;
}
void update(int u, int l, int r, int pl, int pr, int x) {
int mid = l + r >> 1;
if (pl <= l && r <= pr) {
if (!tr[u].id) {
tr[u].id = x;
return;
}
if (compare(x, tr[u].id, mid)) swap(tr[u].id, x);
if (compare(x, tr[u].id, l)) update(u << 1, l, mid, pl, pr, x);
if (compare(x, tr[u].id, r)) update(u << 1 | 1, mid + 1, r, pl, pr, x);
return;
}
if (pl <= mid) update(u << 1, l, mid, pl, pr, x);
if (pr > mid) update(u << 1 | 1, mid + 1, r, pl, pr, x);
}
int query(int u, int l, int r, int x) {
if (l == r) return tr[u].id;
int mid = l + r >> 1;
int ans = tr[u].id;
if (x <= mid) {
int ans2 = query(u << 1, l, mid, x);
if (compare(ans, ans2, x)) return ans;
else return ans2;
}
else {
int ans2 = query(u << 1 | 1, mid + 1, r, x);
if (compare(ans, ans2, x)) return ans;
else return ans2;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
int opt, x1, y1, x2, y2, lastans = 0, cnt = 0;
for (int i = 1; i <= q; i++) {
cin >> opt;
if (opt == 0) {
cin >> x1;
x1 = (x1 + lastans - 1) % 39989 + 1;
cout << (lastans = query(1, 1, 40000, x1)) << '\n';
}
else {
cin >> x1 >> y1 >> x2 >> y2;
x1 = (x1 + lastans - 1) % 39989 + 1;
x2 = (x2 + lastans - 1) % 39989 + 1;
y1 = (y1 + lastans - 1) % 1000000000 + 1;
y2 = (y2 + lastans - 1) % 1000000000 + 1;
if (x1 > x2) swap(x1, x2), swap(y1, y2);
cnt++;
if (x1 == x2) b[cnt] = max(y1, y2);
else {
k[cnt] = 1.0 * (y1 - y2) / (x1 - x2);
b[cnt] = y1 - k[cnt] * x1;
}
update(1, 1, 40000, x1, x2, cnt);
}
}
return 0;
}