跳转至

李超线段树

李超线段树用于维护平面上的直线，支持两种操作：

  • 插入一条线段或直线；
  • 给定 \(k\)，查询与直线 \(x=k\) 相交的所有线段/直线中，交点的 \(y\) 坐标最大/最小的一个。

使用线段树维护区间操作的核心是实现标记的下传。在李超线段树中，我们在每个节点处至多记录一条直线，表示父亲传下来的直线中，在区间中点处取值最小的一条直线。

考虑如何实现下传。若当前节点已经有一条直线了，那么：

  • 先比较两条直线在中点处的取值大小，若传下来的更优，则交换二者；
  • 若传入的直线在左端点处取值更优，则向左区间递归传入；
  • 若传入的直线在右端点处取值更优，则向右区间递归传入；

注意到在第一步之后，传入的直线不可能在两端点同时比原直线更优，因此后两步至多有一步会进行，保证了递归是单侧的，因此单次 move_tag 的时间复杂度为 \(O(\log n)\)。

上面的步骤都没有考虑一次函数的定义域。对于线段，我们先把它拍到线段树上，分解成 \(O(\log V)\) 个区间，然后在每个区间分别下传即可。因此对于插入直线，时间复杂度为 \(O(\log V)\)；对于插入线段，时间复杂度为 \(O(\log n\log V)\)。

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

模板 
  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
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include<iostream>
#define ld long double
using namespace std;
const int N = 1e5 + 10;
const int M = 4e4 + 10;
const int V = 4e4;
const ld eps = 1e-9;

struct Line {
    ld k, b;
} a[N];
int nn;

struct myPair {
    ld v;
    int id;
    inline myPair(ld _p1 = 0, int _p2 = 0) : v(_p1), id(_p2) {}
    inline bool operator<(const myPair &b) const {
        if(abs(v - b.v) > eps) return v < b.v;
        return id > b.id;
    }
};

inline ld calc(int id, int x) {
    return a[id].k * x + a[id].b;
}

namespace SegT {
    int s[4 * M];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void move_tag(int p, int l, int r, int id) {
        if(!s[p]) {
            s[p] = id;
            return;
        }
        int mid = (l + r) >> 1;
        if((myPair){calc(s[p], mid), s[p]} < (myPair){calc(id, mid), id}) swap(id, s[p]);
        if(l == r) return;
        if((myPair){calc(s[p], l), s[p]} < (myPair){calc(id, l), id}) move_tag(lc(p), l, mid, id);
        if((myPair){calc(s[p], r), s[p]} < (myPair){calc(id, r), id}) move_tag(rc(p), mid + 1, r, id);
    }
    void insert(int p, int l, int r, int ql, int qr, int id) {
        if(ql <= l && r <= qr) {
            move_tag(p, l, r, id);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) insert(lc(p), l, mid, ql, qr, id);
        if(mid < qr) insert(rc(p), mid + 1, r, ql, qr, id);
    }
    myPair query(int p, int l, int r, int q) {
        if(l == r) return (myPair){calc(s[p], q), s[p]};
        int mid = (l + r) >> 1;
        if(q <= mid) return max((myPair){calc(s[p], q), s[p]}, query(lc(p), l, mid, q));
        else return max((myPair){calc(s[p], q), s[p]}, query(rc(p), mid + 1, r, q));
    }
}

void insert(int x0, int y0, int x1, int y1) {
    ++nn;
    if(x0 > x1) swap(x0, x1), swap(y0, y1);
    if(x0 == x1) {
        a[nn].k = 0;
        a[nn].b = max(y0, y1);
    } else {
        a[nn].k = (ld)(y1 - y0) / (x1 - x0);
        a[nn].b = y0 - a[nn].k * x0;
    }
    SegT::insert(1, 1, V, x0, x1, nn);
}

int query(int k) {
    return SegT::query(1, 1, V, k).id;
}

int T;

int main() {

    const int MOD1 = 39989;
    const int MOD2 = 1e9;
    int lstans = 0;

    cin >> T;
    while(T--) {
        int op, k, x0, y0, x1, y1;
        cin >> op;
        if(op == 0) {
            cin >> k;
            k = (k + lstans - 1 + MOD1) % MOD1 + 1;
            cout << (lstans = query(k)) << '\n';
        } else {
            cin >> x0 >> y0 >> x1 >> y1;
            x0 = (x0 + lstans - 1 + MOD1) % MOD1 + 1;
            x1 = (x1 + lstans - 1 + MOD1) % MOD1 + 1;
            y0 = (y0 + lstans - 1 + MOD2) % MOD2 + 1;
            y1 = (y1 + lstans - 1 + MOD2) % MOD2 + 1;
            insert(x0, y0, x1, y1);
        }
    }

    return 0;
}

250717 模拟赛 T4

见标题链接。

P4069 [SDOI2016] 游戏

树剖套李超线段树，时间复杂度 \(O(n\log^3 n)\)。