leetcode-go/leetcode/hard/732.cc

#include <iostream>
#include <vector>

using std::vector;
using std::cout; using std::endl;

class MyCalendarThree {
public:
    MyCalendarThree() {
        root = build();
    }

    int book(int start, int end) {
        // end is not included, so -1
        update(root, 1, 0, N, start, end - 1);
        return query(root, 0, N, 0, N);
    }

    void print() {
        for (int i = 0; i < st.size(); i++) {
            SegNode node = st[i];
            cout << "pos: " << i << ", k: " << node.k << ", lazy: " << node.lazy << ", lc: " << node.lc << ", rc: " << node.rc << endl;
        }
    }

private:
    struct SegNode {
        // "lazy" only apply to children, not node itself
        int lazy;
        int k;
        int lc;
        int rc;
    };

    vector<SegNode> st;

    // 10 ^ 9
    static constexpr int N = 1000000000;

    int root;

    int build() {
        int pos = st.size();
        st.push_back(SegNode{});
        return pos;
    }

    void push_down(int pos) {
        if (st[pos].lc == 0) st[pos].lc = build();
        if (st[pos].rc == 0) st[pos].rc = build();
        st[st[pos].lc].lazy += st[pos].lazy;
        st[st[pos].rc].lazy += st[pos].lazy;
    }

    void push_up(int pos) {
        if (st[pos].lc != 0) st[pos].k = std::max(st[pos].k, st[st[pos].lc].k);
        if (st[pos].rc != 0) st[pos].k = std::max(st[pos].k, st[st[pos].rc].k);
    }

    void update(int pos, int val, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            st[pos].k += val;
            st[pos].lazy += val;
            return;
        }
        if (st[pos].lazy != 0) {
            push_down(pos);
            st[st[pos].lc].k += st[pos].lazy;
            st[st[pos].rc].k += st[pos].lazy;
            st[pos].lazy = 0;
        }
        int mid = l + (r - l) / 2;
        if (ql <= mid) {
            if (st[pos].lc == 0) st[pos].lc = build();
            update(st[pos].lc, val, l, mid, ql, qr);
        }
        if (mid < qr) {
            if (st[pos].rc == 0) st[pos].rc = build();
            update(st[pos].rc, val, mid + 1, r, ql, qr);
        }
        push_up(pos);
    }

    int query(int pos, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return st[pos].k;
        if (st[pos].lazy != 0) {
            push_down(pos);
            st[st[pos].lc].k += st[pos].lazy;
            st[st[pos].rc].k += st[pos].lazy;
            st[pos].lazy = 0;
        }
        int mid = l + (r - l) / 2;
        int ans = 0;
        if (ql <= mid) {
            if (st[pos].lc == 0) st[pos].lc = build();
            ans = std::max(ans, query(st[pos].lc, l, mid, ql, qr));
        }
        if (mid < qr) {
            if (st[pos].rc == 0) st[pos].rc = build();
            ans = std::max(ans, query(st[pos].rc, mid + 1, r, ql, qr));
        }
        return ans;
    }
};


// [26,35],[26,32],[25,32],[18,26],[40,45],[19,26],[48,50],[1,6],[46,50],[11,18]
//      1       2       3       3       3       3       3     3       3       3
// 1   5  11  17  18  19  25  26  31  34  40  44  46  48  49
//                            ----------
//                            ------
//                        ----------
//                ----------
//                                        ------
//                    ------
//                                                    ------
// -----
//                                                ----------
//        ----------
int main() {
    MyCalendarThree* sol = new MyCalendarThree();

    cout << "actual: " << sol->book(26,35) << ", expected: " << 1 << endl;
    cout << "actual: " << sol->book(26,32) << ", expected: " << 2 << endl;
    cout << "actual: " << sol->book(25,32) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(18,26) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(40,45) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(19,26) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(48,50) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(1,6) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(46,50) << ", expected: " << 3 << endl;
    cout << "actual: " << sol->book(11,18) << ", expected: " << 3 << endl;

    return 0;
}