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; } };