Add Li-Chao Tree

[tylerm390]

My Implementation from Latin America 2023: Analyzing Contracts

template<class F>
struct node {
    int lo, md, hi;
    F f;
    node *left, *right;
    node(int lo, int hi): lo(lo), hi(hi), md((lo + hi)>>1) {
        if(lo == hi) return;
        left = new node(lo, md);
        right = new node(md+1, hi);
    }
    void update(F g) {
        if(g(md) > f(md)) swap(g, f);
        if(lo == hi) return;

        if(g(lo) < f(lo) && g(hi) < f(hi)) return;

        if(g(lo) > f(lo)) left->update(e);
        else right->update(e);
    }
    void rangeUpdate(F g, int L, int R) {
        if(R < lo || hi < L) return;
        if(L <= lo && hi <= R) return update(g);
        left->rangeUpdate(g, L, R);
        right->rangeUpdate(g, L, R);
    }
    ll query(int x) {
        if(lo == hi) return f(x);
        return max(f(x), (x <= md ? left : right)->query(x));
    }
};