李超线段树（+合并）

__xzm__ · 2025-04-19 17:21:07 · 算法·理论

struct node {
    int l, r; LL k, b;
} z[N*20];

void modify(int &p, int l, int r, LL k, LL b) {
    if (!p) {
        p = ++idx, z[p] = {0, 0, k, b};
        return;
    }
    int mid = (l+r)>>1;
    if (z[p].k*mid+z[p].b > k*mid+b) {
        swap(z[p].k, k), swap(z[p].b, b);
    }
    if (l == r) return;
    if (k > z[p].k) modify(z[p].l, l, mid, k, b);
    else if (k < z[p].k) modify(z[p].r, mid+1, r, k, b);
}

LL query(int p, int l, int r, int x) {
    if (!p) return 1e18;
    int mid = (l+r)>>1;
    LL res = z[p].k*x+z[p].b;
    if (x <= mid) res = min(res, query(z[p].l, l, mid, x));
    else res = min(res, query(z[p].r, mid+1, r, x));
    return res;
}

void merge(int &p, int q, int l, int r) {
    if (!p || !q) {
        p |= q; return;
    }
    int mid = (l+r)>>1;
    merge(z[p].l, z[q].l, l, mid);
    merge(z[p].r, z[q].r, mid+1, r);
    modify(p, l, r, z[q].k, z[q].b);
}