李超树简单笔记

之前一直以为这个树是个什么新的数据结构，今天看了看才发现好像就是一个标记永久化的线段树

解决的经典问题就是平面n条线段，支持在线加边，然后询问x位置的ymax

如果只n条直线的话应该也可以平衡树做

线段树按x轴建，插入新的线段的时候到某个区间，若区间空，则覆盖；若新的严格好于旧的，则覆盖；若有交点，就稍微讨论一下，把不确定的半个区间下放到孩子。最后取根到叶子路径上的所有直线max

#include<bits/stdc++.h>

#define maxn 500010
#define db long double
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
using namespace std;
int n, m;
struct node {
    db k, b;
    int has;
} s[maxn * 4];

int dcmp(db x) {
    if (fabs(x) <= 1e-6)return 0;
    if (x > 0)return 1;
    else return -1;
}

db get(db k1, db b1, db k2, db b2) {
    if (dcmp(k1 - k2) == 0)return -1;
    return (b2 - b1) / (k1 - k2);
}

void Build(int k, int l, int r) {
    s[k].has = 0;
    if (l == r)return;
    Build(lc, l, mid);
    Build(rc, mid + 1, r);
}

void Insert(int k, int l, int r, db K, db B) {
    if (s[k].has == 0) {
        s[k].has = 1;
        s[k].k = K;
        s[k].b = B;
        return;
    }
    if (l == r) {
        if (s[k].k * l + s[k].b < K * l + B) {
            s[k].k = K;
            s[k].b = B;
        }
        return;
    }
    db c = get(s[k].k, s[k].b, K, B);
    if (c < l && c > r) {
        if (dcmp(s[k].k - K) < 0) {
            s[k].k = K;
            s[k].b = B;
        }
    } else if (c <= mid) {
        if (dcmp(s[k].k - K) >= 0) {
            Insert(lc, l, mid, K, B);
        } else {
            Insert(lc, l, mid, s[k].k, s[k].b);
            s[k].k = K;
            s[k].b = B;
        }
    } else {
        if (dcmp(s[k].k - K) >= 0) {
            Insert(rc, mid + 1, r, s[k].k, s[k].b);
            s[k].k = K;
            s[k].b = B;
        } else {
            Insert(rc, mid + 1, r, K, B);
        }
    }
}

db Query(int k, int l, int r, int x) {
    if (s[k].has == 0)return 0;
    db res = s[k].k * x + s[k].b;
    if (l == x && r == x) return res;
    if (x <= mid)res = max(res, Query(lc, l, mid, x));
    else res = max(res, Query(rc, mid + 1, r, x));
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> m;
    n = 50000;
    string s;
    db k, b;
    int x;
    Build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> s;
        if (s == "Project") {
            cin >> b >> k;
            b -= k;
            Insert(1, 1, n, k, b);
        } else {
            cin >> x;
            if (x < 1 || x > n) {
                cout << 0 << endl;
                continue;
            }
            cout << int(Query(1, 1, n, x) / 100) << endl;
        }
    }
    return 0;
}
/*
6
Project 5 0
Project 1 1

Query 4
 Project 100 0
Query 10
Query 110
 */