李超线段树

简介

大概就是用线段树维护二维平面上的线段

李超树所能支持的操作

添加一个线段

查询横坐标为 $x_0$ 时，所有线段的纵坐标的最大值

大概就是我对于线段树上的每个区间维护在这个区间的中点纵坐标最大的线段

然后我将这个东西标记永久化一下就得到了常见的李超树板子

模板

以 Luogu P4097 [HEOI2013]Segment 为例

#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 100010
#define eps 1e-6
#define INF 1000000000
using namespace std;

const int N = 39989;

int m;

struct Line {
    double k, b;
};

double F(const Line &l, int x) { return x * l.k + l.b; }

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    int v;
    Line l; 
} T[maxn * 4];
void update(int i, int l, int r, int L, int R, Line d, int v) {
    if (l > R || r < L) return ; int m = l + r >> 1; 
    if (L <= l && r <= R) {
        double tl = F(d, l), tr = F(d, r);
        double sl = F(T[i].l, l), sr = F(T[i].l, r);
        if (tl > sl && tr > sr) return (void) (T[i] = { v, d }); //比较在 l 和 r 处的值，如果都大于，就替换
        if (sl > tl && sr > tr) return ; // 否则直接走
        double tm = F(d, m), sm = F(T[i].l, m); // 比较在中点的值
        if (tm > sm) swap(T[i].l, d), swap(T[i].v, v); //保留较大的，然后向下传另一个
        if (d.k < T[i].l.k) update(lc, l, m, L, R, d, v); //如果 l1 的斜率大于 l2，则向左
        else update(rc, m + 1, r, L, R, d, v); // 否则向右
        return ;
    }
    update(lc, l, m, L, R, d, v); update(rc, m + 1, r, L, R, d, v); 
}

double mx; int lans; 
void query(int i, int l, int r, int k) {
    if (F(T[i].l, k) > mx) mx = F(T[i].l, k), lans = T[i].v;
    else if (fabs(F(T[i].l, k) - mx) < eps) lans = min(lans, T[i].v);
    if (l == r) return ; int m = l + r >> 1; 
    if (k <= m) query(lc, l, m, k);
    else query(rc, m + 1, r, k); 
} 

inline void solve_1() {
    int x; cin >> x; x = (x + lans - 1) % N + 1;
    mx = lans = 0; query(1, 1, N, x); 
    cout << lans << "\n";
}

int cnt;
inline void solve_2() {
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    x1 = (x1 + lans - 1) % N + 1; x2 = (x2 + lans - 1) % N + 1;
	y1 = (y1 + lans - 1) % INF + 1; y2 = (y2 + lans - 1) % INF + 1;
    if (x1 > x2) swap(x1, x2), swap(y1, y2);
    Line l; ++cnt;
    if (x1 == x2) l = { 0, (double) max(y1, y2) };
    else l.k = 1.0 * (y2 - y1) / (x2 - x1), l.b = y1 - l.k * x1;
    update(1, 1, N, x1, x2, l, cnt);
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 0) solve_1();
        else solve_2();
    } 
    return 0;
}