力扣218.天际线问题 线段树区间修改、单点查询、离散化、最大值

https://leetcode-cn.com/problems/the-skyline-problem/submissions/

class Solution {
private:
    class SegmentTree {
    private:
        struct node {
            int l, r, h, lz;
        };
        vector<node> tree;
    public:    
        SegmentTree(int n) {
            tree.resize(n * 4);
        }

        inline int ls(int x) {
            return x << 1;
        }

        inline int rs(int x) {
            return (x << 1) | 1;
        }

        void push_down(int root) {
            if (tree[root].lz > 0) {
                tree[ls(root)].h = max(tree[ls(root)].h, tree[root].lz);
                tree[rs(root)].h = max(tree[rs(root)].h, tree[root].lz);
                tree[ls(root)].lz = max(tree[ls(root)].lz, tree[root].lz);
                tree[rs(root)].lz = max(tree[rs(root)].lz, tree[root].lz);
            }
            tree[root].lz = 0;
        }

        void push_up(int root) {
            tree[root].h = max(tree[root].h, tree[ls(root)].h);
            tree[root].h = max(tree[root].h, tree[rs(root)].h);
        }



        void build(int root, int l, int r) {
            tree[root].l = l;
            tree[root].r = r;
            tree[root].h = 0;
            if (l == r) {
                return;
            }

            int mid = (l + r) / 2;
            build(ls(root), l, mid);
            build(rs(root), mid + 1, r);
        }

        void update(int root, int l, int r, int h) {
            if (tree[root].l == l && tree[root].r == r) {
                tree[root].h = max(tree[root].h, h);
                tree[root].lz = max(h, tree[root].lz);
                return;
            }

            int mid = (tree[root].l + tree[root].r) / 2;
            push_down(root);

            if (r <= mid) {
                update(ls(root), l, r, h);
            }
            else if (l > mid) {
                 update(rs(root), l, r, h);
            }
            else {
                update(ls(root), l, mid, h);
                update(rs(root), mid + 1, r, h);
            }

            push_up(root);
        }

        int query(int root, int l, int r) {
            if (tree[root].l == l && tree[root].r == r) {
                return tree[root].h;
            }
            push_down(root);
            int mid = (tree[root].l + tree[root].r) / 2;

            if (l > mid) {
                return query(rs(root), l, r);
            }
            else if (r <= mid) {
                return query(ls(root), l, r);
            }
            else {
                return max(query(ls(root), l, mid), query(rs(root), mid + 1, r));
            }

            push_up(root);
        }

    };

private:
    vector<int> axis;    //离散化坐标轴
    int find(int x) {
        //坐标轴从1开始
        return lower_bound(axis.begin(), axis.end(), x) - axis.begin() + 1;
    }

public:
    vector<vector<int>> getSkyline(vector<vector<int>> buildings) {
        for (auto &v : buildings) {
            axis.push_back(v[0]);
            axis.push_back(v[1]);
            axis.push_back(v[1] - 1);
        }
        sort(axis.begin(), axis.end());
        axis.erase(unique(axis.begin(), axis.end()), axis.end());

        int n = axis.size();
        SegmentTree tree(n);
        tree.build(1, 1, n);

        for (auto &v : buildings) {
            int l = find(v[0]);
            int r = find(v[1] - 1);

            tree.update(1, l, r, v[2]);
        }

        int pre = 0;
        vector<vector<int>> ans;

        for (int i = 0; i < axis.size(); ++i) {
            int h = tree.query(1, i + 1, i + 1);    //单点查询
            if (pre != h) {
                ans.push_back({axis[i], h});
                pre = h;
            }
        }

        return ans;
    }
};