李超线段树

李超线段树

俗称线段线段树，用于维护区间加线段的操作。

实际上他的核心思想就是二分。考虑对于一条线段我们最多可以将他划分成 $\log{n}$ 段，然后我们有需要花费 $\log{n}$ 的时间去更新答案（主要是依赖对半后递归实现）。所以实际时间复杂度为 $\text{O}(n \cdot { \log{n} }^2)$。

对半实现的细节进行分类讨论：

1. 如果插入线段完全大于当前结点线段，直接覆盖并跳出递归；
2. 如果插入线段完全小于当前结点线段，直接跳出递归；
3. 如果插入线段的左半部分与当前结点线段有交点，判断右半部分是否覆盖后继续递归左子区间；
4. 如果插入线段的右半部分与当前结点线段有交点，判断左半部分是否覆盖后继续递归右子区间。

然而实现上有许多细节，我们可以考虑类似于线段树的另一种写法，大概就是直接向左右子区间递归后，在递归函数的开头考虑是否跳出递归。

模板题 P4097 [HEOI2013]Segment

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 1e5 + 1e1, Mod = 39989, mod = 1e9;
const lint INF = 1e18 + 1e9;

struct Segment {
    double k, b;
    int l, r, id, book;
} ;
struct Pair {
    double h;
    int id;
} ;
int n, cnt, lastans;

struct SegmentTree {
    Segment tree[MAXN << 2];

    void Build(int l, int r, int x) {
        tree[x].l = l, tree[x].r = r, tree[x].id = 0, tree[x].book = false;
        if (l == r) ;
        else {
            int mid = l + r >> 1;
            Build(l, mid, x << 1), Build(mid + 1, r, x << 1 | 1);
        }
        return ;
    }

    void Pushdown(double k, double b, int id, int x) {
        int l = tree[x].l, r = tree[x].r;
        if (!tree[x].book) tree[x].k = k, tree[x].b = b, tree[x].id = id, tree[x].book = true;
        else {
            double k0 = tree[x].k, b0 = tree[x].b;
            double l0 = k0 * l + b0, r0 = k0 * r + b0, l1 = k * l + b, r1 = k * r + b;
            if (l1 > l0 && r1 > r0) tree[x].k = k, tree[x].b = b, tree[x].id = id;
            else {
                if (l0 >= l1 && r0 >= r1) ;
                else Pushdown(k, b, id, x << 1), Pushdown(k, b, id, x << 1 | 1);
            }
        }
        return ;
    }

    void Update(int ql, int qr, double k, double b, int id, int x) {
        int l = tree[x].l, r = tree[x].r;
        if (qr < l || r < ql) return ;
        if (ql <= l && r <= qr) Pushdown(k, b, id, x);
        else Update(ql, qr, k, b, id, x << 1), Update(ql, qr, k, b, id, x << 1 | 1);
        return ;
    }

    Pair Query(int ql, int qr, int x) {
        int l = tree[x].l, r = tree[x].r;
        Pair res = (Pair){0.0, 0};
        if (qr < l || r < ql) return res;
        double k = tree[x].k, b = tree[x].b;
        res = (Pair){k * ql + b, tree[x].id};
        if (ql <= l && r <= qr) ;
        else {
            Pair ls = Query(ql, qr, x << 1), rs = Query(ql, qr, x << 1 | 1);
            if (fabs(res.h - ls.h) < 1e-6) res.id = min(ls.id, res.id);
            else if (res.h < ls.h) res = ls;
            if (fabs(res.h - rs.h) < 1e-6) res.id = min(rs.id, res.id);
            else if (res.h < rs.h) res = rs;
        }
        return res;
    }
} st;

int main(void) {

    scanf("%d", &n);
    st.Build(1, Mod + 10, 1);
    for (int i = 1; i <= n; i ++) {
        int op = readint;
        if (op) {
            int x0 = readint, y0 = readint, x1 = readint, y1 = readint, id = (++ cnt);
            x0 = (x0 + lastans - 1) % Mod + 1, y0 = (y0 + lastans - 1) % mod + 1;
            x1 = (x1 + lastans - 1) % Mod + 1, y1 = (y1 + lastans - 1) % mod + 1;
            if (x0 == x1) st.Update(x0, x1, 0.0, 1.0 * max(y0, y1), id, 1);
            else {
                if (x0 > x1) swap(x0, x1), swap(y0, y1);
                double k = 1.0 * (y0 - y1) / (x0 - x1), b = 1.0 * y0 - k * x0;
                st.Update(x0, x1, k, b, id, 1);
            }
        }
        else {
            int k = (readint + lastans - 1) % Mod + 1;
            lastans = st.Query(k, k, 1).id;
            printf("%d\n", lastans);
        }
    }

    return 0;
}