李超线段树

引言

在很长一段时间，我一直都以为 $\text{Link-Cut Tree}$ 和李超线段树是一个东西，毕竟都是 $\text{LCT}$。（雾

直到学了 $\text{Link-Cut Tree}$ 才知道两者不是一个东西，虽然当时很好奇李超线段树是啥，但因为比较菜，一直到今天才学……

原理

总所周知，李超线段树是一颗线段树。

李超线段树是用来解决如下问题的：

给定一个平面直角坐标系，支持动态插入一条线段，对于每一个询问，给一条竖线，问这条竖线与所有线段的最高的交点（即 $y$ 值最大）。

如上图，两条蓝色的直线就是两个询问，那么答案分别就是 $A$ 点和 $B$ 点。

我们先引入一个概念，最优势线段，就是当前区间中点处最高的线段。

李超线段树维护的是当前区间的最优势线段。

因为李超线段树维护的是当前区间的最优势线段，而当前区间的最优势线段，在接下来分成的两个区间里不一定是最优势线段，所以对于普通线段树的下传标记操作，在李超线段树里是不存在的。

但是呢，在李超线段树里面，维护的不一定是当前区间的最优势线段，当前区间的最优势线段在当前区间及其所有祖先区间的最优势线段之中，具体原因是因为在动态插入线段时为了能够做到 ${\log }^{2}n$ 的时间复杂度，它并不会更新所有的区间。

我们先来看看如何插入线段。

我们会分为以下几种情况：

• 该线段与当前线段树枚举到的区间不相交，此时直接返回即可。

• 该线段覆盖部分当前线段树枚举到的区间，递归到左右子区间继续处理。

• 该线段完全覆盖当前线段树枚举到的区间，则继续分类

  • 该线段在两个端点处值均比当前区间的最优势线段更大，则当前区间的最优势线段设为该线段，然后返回。
  • 该线段在两个端点处的值均比当前区间的最优势线段更小，则返回。
  • 该线段与当前区间的最优势线段比较，如果在中点处该线段更优，则交换该线段和当前区间的最优势线段（将当前区间的最优势线段替换为该线段，将该线段设为当前区间的最优势线段），如果在中点处当前区间的最优势线段更优，则不更改。然后再判断左右端点处的值，如果在该侧该线段比当前权健的最优势线段更优，则递归该侧。

这样子我们动态插入线段就搞定了，可以参照下面代码理解理解：

bool pd(int i, int j, int x) {
	//即比较两个线段在该位置的大小，由于精度问题，需要特殊处理一下，不然会被卡
    if (a[i].k * x + a[i].b - a[j].k * x - a[j].b > eps)
        return true;
    if (a[j].k * x + a[j].b - a[i].k * x - a[i].b > eps)
        return false;
    return i < j;
}
void change(int &x, int l, int r, int sl, int sr, int now) {
	//now是插入线段的编号
    if (r < sl || sr < l)//不相交
        return ;
    if (!x)//动态开点
        x = ++Tcnt;
    if (sl <= l && r <= sr) {//完全覆盖
        if (pd(now, tr[x].id, l) && pd(now, tr[x].id, r)) {
            tr[x].id = now;
            return ;
        }
        if (pd(tr[x].id, now, l) && pd(tr[x].id, now, r))
            return ;
        int mid = (l + r) >> 1;
        if (pd(now, tr[x].id, mid))
            swap(now, tr[x].id);
        if (pd(now, tr[x].id, l))
            change(tr[x].ls, l, mid, sl, sr, now);
        if (pd(now, tr[x].id, r))
            change(tr[x].rs, mid + 1, r, sl, sr, now);
    }
    else {//覆盖部分
        int mid = (l + r) >> 1;
        change(tr[x].ls, l, mid, sl, sr, now), change(tr[x].rs, mid + 1, r, sl, sr, now);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

查询就更简单了，直接往下找到该区间，并且将路径上所有区间的最优势线段都拿出来比较一下，可以参照下面代码理解。

void solve(int x, int l, int r, int s) {
    if (!x || r < s || s < l)
        return ;
    if (pd(tr[x].id, ansid, s))//这里记录的是编号
        ansid = tr[x].id;
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    solve(tr[x].ls, l, mid, s), solve(tr[x].rs, mid + 1, r, s);
}
1
2
3
4
5
6
7
8
9
10

到这里，李超线段树就完成了！！！

其实对于所有的斜率优化 $\text{DP}$，都可以用李超线段树解决，只是时间会套上 ${\log }^{2}n$。

接下来可以看几道例题，上面的代码片段是下面的第一道例题的。

例题

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

版题，没什么好说的，直接上代码。

唯一的坑点就是精度问题。

#include 
using namespace std;
const double eps = 1e-9;
int T, Lastans, n = 39989, m, Tcnt, Rt, ansid;
struct Line { double k, b; } a[1000005];
struct Tree { int ls, rs, id; } tr[10000005];
bool pd(int i, int j, int x) {
    if (a[i].k * x + a[i].b - a[j].k * x - a[j].b > eps)
        return true;
    if (a[j].k * x + a[j].b - a[i].k * x - a[i].b > eps)
        return false;
    return i < j;
}
void change(int &x, int l, int r, int sl, int sr, int now) {
    if (r < sl || sr < l)
        return ;
    if (!x)
        x = ++Tcnt;
    if (sl <= l && r <= sr) {
        if (pd(now, tr[x].id, l) && pd(now, tr[x].id, r)) {
            tr[x].id = now;
            return ;
        }
        if (pd(tr[x].id, now, l) && pd(tr[x].id, now, r))
            return ;
        int mid = (l + r) >> 1;
        if (pd(now, tr[x].id, mid))
            swap(now, tr[x].id);
        if (pd(now, tr[x].id, l))
            change(tr[x].ls, l, mid, sl, sr, now);
        if (pd(now, tr[x].id, r))
            change(tr[x].rs, mid + 1, r, sl, sr, now);
    }
    else {
        int mid = (l + r) >> 1;
        change(tr[x].ls, l, mid, sl, sr, now), change(tr[x].rs, mid + 1, r, sl, sr, now);
    }
}
void solve(int x, int l, int r, int s) {
    if (!x || r < s || s < l)
        return ;
    if (pd(tr[x].id, ansid, s))
        ansid = tr[x].id;
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    solve(tr[x].ls, l, mid, s), solve(tr[x].rs, mid + 1, r, s);
}
int main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        int id;
        scanf("%d", &id);
        if (id == 0) {
            int x;
            ansid = 0;
            scanf("%d", &x), x = (x + Lastans - 1) % n + 1;
            solve(1, 1, n, x), Lastans = ansid;
            printf("%d\n", ansid);
        }
        else {
            int sx, sy, ex, ey;
            scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
            sx = (sx + Lastans - 1) % n + 1, sy = (sy + Lastans - 1) % 1000000000 + 1, ex = (ex + Lastans - 1) % n + 1, ey = (ey + Lastans - 1) % 1000000000 + 1;
            if (ex < sx)
                swap(sx, ex), swap(sy, ey);
            if (ex != sx)
                m++, a[m].k = 1.0 * (ey - sy) / (ex - sx), a[m].b = 1.0 * sy - a[m].k * sx;
            else
                m++, a[m].k = 0, a[m].b = max(sy, ey);
            // a[m].k *= 10, a[m].b *= 10;
            change(Rt, 1, n, sx, ex, m);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

P4254 [JSOI2008] Blue Mary 开公司

也是一道版题，就是输入的时候要先减去一次 $P$，因为是从第一天开始的。

#include 
using namespace std;
const double eps = 1e-9;
int T, cnt, Tcnt, Rt;
struct Line { double k, b; } a[100005];
struct Tree { int ls, rs, id; } tr[2000005];
char s[25];
bool pd(int i, int j, int s) {
    if (a[i].k * s + a[i].b - a[j].k * s - a[j].b > eps)
        return true;
    if (a[j].k * s + a[j].b - a[i].k * s - a[i].b > eps)
        return false;
    return i < j;
}
void change(int &x, int l, int r, int now) {
    if (!x)
        x = ++Tcnt;
    if (pd(now, tr[x].id, l) && pd(now, tr[x].id, r)) {
        tr[x].id = now;
        return ;
    }
    if (pd(tr[x].id, now, l) && pd(tr[x].id, now, r))
        return ;
    int mid = (l + r) >> 1;
    if (pd(now, tr[x].id, mid))
        swap(now, tr[x].id);
    if (pd(now, tr[x].id, l))
        change(tr[x].ls, l, mid, now);
    if (pd(now, tr[x].id, r))
        change(tr[x].rs, mid + 1, r, now);
}
int solve(int x, int l, int r, int s) {
    if (r < s || s < l)
        return 0;
    int mid = (l + r) / 2, t = a[tr[x].id].k * s + a[tr[x].id].b;
    if (l == r)
        return t;
    return max(t, max(solve(tr[x].ls, l, mid, s), solve(tr[x].rs, mid + 1, r, s)));
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s + 1);
        if (s[1] == 'P')
            cnt++, scanf("%lf%lf", &a[cnt].b, &a[cnt].k), a[cnt].b -= a[cnt].k, change(Rt, 1, 50000, cnt);
        else {
            int x;
            scanf("%d", &x);
            printf("%d\n", solve(1, 1, 50000, x) / 100);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53