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

Glacial_Shine · 2023-09-20 22:19:39 · 题解

2025.1.16 UPD：之前的描述有些许笼统，修改了一下使其更为详细。

来本蒟蒻的博客看看吧！！！

这是一个版题，既然是版题，那就得讲讲这个算法。（废话

引言

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

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

原理

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

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

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

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

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

李超线段树维护的是有可能成为当前区间的最优势线段。某个节点的最优势线段在这个节点到根节点路径上所有最优势线段的之中。

为什么要这样维护呢？

因为不这样做的话加入一个线段你就要遍历整个区间，此时时间复杂度就会退化的十分严重（可能到 n^2）。

而如果像我们这样子维护的话，我们就不用每次加入线段都遍历整个区，而是可以在一个可以替换的区间停下。

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

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

• 该线段与当前线段树枚举到的区间不相交，此时直接返回即可。
• 该线段覆盖部分当前线段树枚举到的区间，递归到左右子区间继续处理。（前两步其实就是将线段用线段树上的区间覆盖）

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

  • 该线段在两个端点处值均比当前区间的最优势线段更大，则将当前区间的最优势线段设为该线段，然后返回。（此时旧的最优势线段已经无用了）
  • 该线段在两个端点处的值均比当前区间的最优势线段更小，则返回。（此时我们新加的线段也已经无用了）
  • 现在只剩下一个端点新加入的线段大，另一个端点区间的最优势线段大的情况，我们可以这样考虑。

  因为我们一个区间存储的是中点位置的最优势线段，所以我们需要判断一下新加入的线段和原先区间的最优势线段在中点位置的大小，并且更新改区间的最优势线段。

  因为这两个线段不能互相替代，所以我们并不能直接将一个线段舍弃，也就是说我们要将没被记录的线段往两边递归，但是由于在中点处未被记录的线段更小，所以在某一边该线段是完全小于被记录的线段的，所以不需要往该边递归，只需要往另一边递归即可。（被记录的线段指的是被存储到该区间的最优势线段，未被记录的线段指的是另一条线段）

  （有点长，耐心点看）

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

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);
    }
}

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

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);
}

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

考虑一下时间复杂度，我们知道线段会在线段树上分成 \log n 个区间，而看到我们插入操作，分成的每个区间不会再分裂，而只会往一边更新，最多更新 \log n 层，所以时间复杂度是 log^2 n。

其实对于所有的斜率优化 \text{DP}，都可以用李超线段树解决，只是时间会套上 \log^2n。（毕竟斜率优化 \text{DP} 本质上是用直线来优化 \text{DP}，这就很能李超树）

然后我们就可以来看这道版题，没什么好说的，直接上代码。

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

#include <bits/stdc++.h>
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;
}