$\LARGE{引入}$
要求在平面直角坐标系下维护两个操作:
- 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。
- 给定一个数 $k$,询问与直线 $x = k$ 相交的线段中,交点纵坐标最大的线段的编号。
李超线段树是用于解决上述问题的特殊线段树。
$\LARGE{过程}$
李超线段树对于一个节点 $[l, r]$,维护的标记是 $x = mid$ 时的答案。
每次插入一个新的线段 $f$ ,先由线段树将其分成被它完全包含的 $O(\log n)$ 段。
对于其中的每一个段修改前的标记 $g$ ,若 $f(mid) > g(mid)$ ,则交换 $f, g$ 。
于是 $f(mid)$ 一定小于 $g(mid)$ ,若交点在左侧则递归左侧,若交点在右侧则递归右侧,最多重复 $O(\log n)$ 次。
查询答案时,在从根到叶子节点的路径上所有点的标记上找出最优的作为答案。
节点维护的标记实际上是一个标记永久化,表示的是还有哪一个线段没有下传。
总时间复杂度为 $O(n\log^2 n)$ 。
$\LARGE{实现}$
以 $luogu$ 模板的 $AC$ 代码为例。
#include <bits/stdc++.h>
#define ggg 1000000000
#define ll long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define re register
#define sz(x) (int(x.size()))
#define all(x) x.begin(), x.end()
#define mst(x, bit) memset(x, bit, sizeof(x))
using namespace std;
const int N = 1e5 + 10, M = 39989;
const double eps = 1e-10;
int m, cnt, lastans;
int rd() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - 48; ch = getchar();}
return f * w;
}
int cmp(double x, double y) {
if (x - y > eps) return 1;
if (y - x > eps) return -1;
return 0;
}
struct segment {
int l, r, b;
double slope;
} seg[N];
double calc(int x, int k) {
if (seg[k].l <= x && x <= seg[k].r)
return seg[k].b + (x - seg[k].l) * seg[k].slope;
return -1;
}
bool cmp2(int k, int x, int y) {
int g = cmp(calc(k, x), calc(k, y));
if (g == 1 || (g == 0 && x < y)) return true;
return false;
}
void add(int x0, int y0, int x1, int y1) {
if (x0 == x1) seg[++ cnt] = {x0, x1, max(y0, y1), 0};
else seg[++ cnt] = {x0, x1, y0, (y1 - y0) * 1.0 / (x1 - x0)};
}
struct Node{
int mvp;
} tr[160010];
void upd(int u, int l, int r, int k) {
int mid = l + r >> 1;
if (cmp2(mid, k, tr[u].mvp)) swap(tr[u].mvp, k);
if (cmp2(l, tr[u].mvp, k) && cmp2(r, tr[u].mvp, k)) return;
if (cmp2(l, k, tr[u].mvp)) upd(u << 1, l, mid, k);
else upd(u << 1 | 1, mid + 1, r, k);
}
void insert(int u, int L, int R, int l, int r, int d) {
if (l <= L && R <= r) {
upd(u, L, R, d);
return;
}
int mid = L + R >> 1;
if (l <= mid) insert(u << 1, L, mid, l, r, d);
if (r > mid) insert(u << 1 | 1, mid + 1, R, l, r, d);
}
int query(int u, int l, int r, int x) {
if (l == r) return tr[u].mvp;
int mid = l + r >> 1, k;
if (x <= mid) k = query(u << 1, l, mid, x);
else k = query(u << 1 | 1, mid + 1, r, x);
return cmp2(x, tr[u].mvp, k) ? tr[u].mvp : k;
}
int main() {
m = rd();
while (m -- ) {
int op = rd();
if (op == 0) printf("%d\n", lastans = query(1, 1, M, (rd() + lastans - 1) % M + 1));
else {
int x0 = (rd() + lastans - 1) % M + 1;
int y0 = (rd() + lastans - 1) % ggg + 1;
int x1 = (rd() + lastans - 1) % M + 1;
int y1 = (rd() + lastans - 1) % ggg + 1;
if (x0 > x1) swap(x0, x1), swap(y0, y1);
add(x0, y0, x1, y1);
insert(1, 1, M, x0, x1, cnt);
}
}
return 0;
}