P4097 【模板】李超线段树 / [HEOI2013] Segment
前言
李超线段树并不是一种新的线段树，而是对一类题维护最值的过程做了改进，使线段树仍然有不错的复杂度。
引入
简要题意
实现两种操作：
- 在区间 \([x_0,y_0]\) 上加入一条两端为 \((x_0,y_0)\)，\((x_1,y_1)\) 的线段。
- 查询下标 \(k\) 上的纵坐标最大的线段的编号。
区别如区间覆盖，每个位置都插入不同的值，如果暴力，每次修改就要 \(O(n\log n)\) 的复杂度。李超线段树就是高效维护这类问题。
考虑线段树上每个节点 \(u\) 的 \(t_u\) 存下标 \(mid\) 上的取到最大值的线段的编号。先考虑修改操作。
现在插入一条线段 \(x\)，那么和普通线段树一样，将 \([x_0,x_1]\) 拆成 \(\log n\) 个区间遍历。
假如此时遍历到的区间为 \([l,r]\)，用新线段 \(x\) 在下标 \(k\) 上的纵坐标与线段 \(t_u\) 比较。如果新线段更大，那么说明至少有一半以上的区间的最大值编号都将是 \(x\)，将 \(t_u\) 与 \(x\) 交换；反之则还是原线段 \(t_u\)。
运用标记永久化的思想，大于一半都是同一个编号的区间就不管了，直接把答案挂在 \(t_u\) 上不往下传了，另一半往下递归，因为线段 \(x\) 的贡献可能不止于此。比如：
原本 \(x\) 现在为红线段，\(t_u\) 为蓝线段，比较了 \(mid\) 上的 \(x\) 和 \(t_u\) 之后，\(x\) 现在为蓝线段，\(t_u\) 为红线段。那么 \([l,mid]\) 不下传了，而此时 \(x\) 并不是没有用，因为在 \([mid,r]\) 之间又超过了红线段。所以继续往下递归 \([mid,r]\)，维护 \(x\) 的贡献。
如何判断是否超过？只需要看两个端点上线段的纵坐标即可。
这样，修改操作就在 \(O(\log^2n)\) 的复杂度下完成了，因为每个区间都需要再递归 \(\log n\) 次维护。
查询操作简单，由于标记永久化，只要比较线段树上到 \([k,k]\) 的路径上的所有线段 \(t_u\) 在下标 \(k\) 上的纵坐标即可，答案一定在路径上。
总复杂度 \(O(n\log^2n)\)。
#include <iostream>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back
using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10, mod1 = 39989, mod2 = 1e9;
int n, cnt;
double eps = 1e-9;
struct line {
double k, b;
} a[N];
int t[N << 2];
int cmp(double x, double y) {
if(x - y > eps) return 1;
if(y - x > eps) return -1;
return 0;
}
double calc(int id, int x) {
return a[id].k * x + a[id].b;
}
void add(int x0, int y0, int x1, int y1) {
if(x0 == x1) {
a[++cnt].k = 0, a[cnt].b = std::max(y0, y1);
} else {
a[++cnt].k = 1.0 * (y1 - y0) / (x1 - x0), a[cnt].b = y0 - a[cnt].k * x0;
}
}
void mdf(int u, int l, int r, int x) {
int mid = (l + r) >> 1;
int bmid = cmp(calc(x, mid), calc(t[u], mid));
if(bmid == 1 || (!bmid && x < t[u])) std::swap(x, t[u]);
int bl = cmp(calc(x, l), calc(t[u], l)), br = cmp(calc(x, r), calc(t[u], r));
if(bl == 1 || (!bl && x < t[u])) mdf(u << 1, l, mid, x);
if(br == 1 || (!br && x < t[u])) mdf(u << 1 | 1, mid + 1, r, x);
}
void update(int u, int l, int r, int L, int R, int x) {
if(L <= l && r <= R) {
mdf(u, l, r, x);
return;
}
int mid = (l + r) >> 1;
if(L <= mid) update(u << 1, l, mid, L, R, x);
if(R > mid) update(u << 1 | 1, mid + 1, r, L, R, x);
}
int mx(int x, int y, int z) {
int ret = cmp(calc(x, z), calc(y, z));
if(ret == 1) return x;
else if(ret == -1) return y;
else return (x < y ? x : y);
}
int qry(int u, int l, int r, int x) {
if(l == r) return t[u];
int mid = (l + r) >> 1;
if(x <= mid) return mx(t[u], qry(u << 1, l, mid, x), x);
else return mx(t[u], qry(u << 1 | 1, mid + 1, r, x), x);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
int lstans = 0;
while(n--) {
int op, x0, y0, x1, y1, k;
std::cin >> op;
if(!op) {
std::cin >> k;
k = (k + lstans - 1) % mod1 + 1;
std::cout << (lstans = qry(1, 1, mod1, k)) << "\n";
} else {
std::cin >> x0 >> y0 >> x1 >> y1;
x0 = (x0 + lstans - 1) % mod1 + 1;
x1 = (x1 + lstans - 1) % mod1 + 1;
y0 = (y0 + lstans - 1) % mod2 + 1;
y1 = (y1 + lstans - 1) % mod2 + 1;
if(x0 > x1) std::swap(x0, x1), std::swap(y0, y1);
add(x0, y0, x1, y1);
update(1, 1, mod1, x0, x1, cnt);
}
}
return 0;
}