leetcode699 掉落的方块

思路：

动态开点线段树，在值域范围很大的时候可以采用此方法。这里维护了区间最大值和区间赋值。

实现：

 1 class SegmentTree {
 2 public:
 3     int N = (int)1e9;
 4     class Node {
 5     public:
 6         // ls 和 rs 分别代表当前区间的左右子节点
 7         Node*ls=nullptr, *rs=nullptr;
 8         // val 代表当前区间的最大高度，add 为懒标记
 9         int val=0, add=0;
10         Node(){}
11     };
12     Node*root = nullptr;
13     SegmentTree(int n){
14         root=new Node();
15         N=n;
16     }
17     void update(int l,int r,int v){
18         _update(root,0,N,l,r,v);
19     }
20     void _update(Node*node, int lc, int rc, int l, int r, int v) {
21         if (l <= lc && rc <= r) {
22             node->add = v;
23             node->val = v;
24             return ;
25         }
26         pushdown(node);
27         int mid = lc + rc >> 1;
28         if (l <= mid) _update(node->ls, lc, mid, l, r, v);
29         if (r > mid) _update(node->rs, mid + 1, rc, l, r, v);
30         pushup(node);
31     }
32     int query(int l,int r){
33         return _query(root,0,N,l,r);
34     }
35     int _query(Node*node, int lc, int rc, int l, int r) {
36         if (l <= lc && rc <= r) return node->val;
37         pushdown(node);
38         int mid = lc + rc >> 1, ans = 0;
39         if (l <= mid) ans = _query(node->ls, lc, mid, l, r);
40         if (r > mid) ans = max(ans, _query(node->rs, mid + 1, rc, l, r));
41         return ans;
42     }
43     void pushdown(Node*node) {
44         if (node->ls == nullptr) node->ls = new Node();
45         if (node->rs == nullptr) node->rs = new Node();
46         if (node->add == 0) return ;
47         node->ls->add = node->add; node->rs->add = node->add;
48         node->ls->val = node->add; node->rs->val = node->add;
49         node->add = 0;
50     }
51     void pushup(Node*node) {
52         node->val = max(node->ls->val, node->rs->val);
53     }
54 
55 };
56 class Solution {
57 public:
58     vector<int>fallingSquares(vectorint>>&ps) {
59         vector<int>res;
60         int N=1e9;
61         SegmentTree*st=new SegmentTree(N);
62         for (auto&info:ps) {
63             int x=info[0],h=info[1],cur=st->query(x,x+h-1);
64             st->update(x,x+h-1,cur+h);
65             res.push_back(st->query(0,N));
66         }
67         return res;
68     }
69 };