P4097 【模板】李超线段树 / [HEOI2013] Segment

前言

李超线段树并不是一种新的线段树，而是对一类题维护最值的过程做了改进，使线段树仍然有不错的复杂度。

引入

简要题意

实现两种操作：

1. 在区间 \([x_0,y_0]\) 上加入一条两端为 \((x_0,y_0)\)，\((x_1,y_1)\) 的线段。
2. 查询下标 \(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;
}