题目描述
这是 LeetCode 上的 699. 掉落的方块 ，难度为 困难。
Tag : 「线段树（动态开点）」、「线段树」
在无限长的数轴（即 x 轴）上，我们根据给定的顺序放置对应的正方形方块。
第 i 个掉落的方块（positions[i] = (left, side_length)）是正方形，其中 left 表示该方块最左边的点位置(positions[i][0])，side_length 表示该方块的边长(positions[i][1])。
每个方块的底部边缘平行于数轴（即 x 轴），并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落，并保持静止后，才开始掉落新方块。
方块的底边具有非常大的粘性，并将保持固定在它们所接触的任何长度表面上（无论是数轴还是其他方块）。邻接掉落的边不会过早地粘合在一起，因为只有底边才具有粘性。
返回一个堆叠高度列表 ans。每一个堆叠高度 ans[i] 表示在通过 positions[0], positions[1], ..., positions[i] 表示的方块掉落结束后，目前所有已经落稳的方块堆叠的最高高度。
示例 1:
输入: [[1, 2], [2, 3], [6, 1]]输出: [2, 5, 5]解释:第一个方块 positions[0] = [1, 2] 掉落：_aa_aa-------方块最大高度为 2 。第二个方块 positions[1] = [2, 3] 掉落：__aaa__aaa__aaa_aa___aa__--------------方块最大高度为5。大的方块保持在较小的方块的顶部，不论它的重心在哪里，因为方块的底部边缘有非常大的粘性。第三个方块 positions[1] = [6, 1] 掉落：__aaa__aaa__aaa_aa_aa___a-------------- 方块最大高度为5。因此，我们返回结果[2, 5, 5]。
示例 2:
输入: [[100, 100], [200, 100]]输出: [100, 100]解释: 相邻的方块不会过早地卡住，只有它们的底部边缘才能粘在表面上。
注意:
$1 <= positions.length <= 1000$
$1 <= positions[i][0] <= 10^8$
$1 <= positions[i][1] <= 10^6$
基本分析
为了方便，我们使用 ps 来代指 positions。
每次从插入操作都附带一次询问，因此询问次数为 $1e3$，左端点的最大值为 $10e8$，边长最大值为 $1e6$，由此可知值域范围大于 $1e8$，但不超过 $1e9$。
对于值域范围大，但查询次数有限的区间和问题，不久前曾经总结过 : 求解常见「值域爆炸，查询有限」区间问题的几种方式，可作为前置 ? 进行了解。
而我的个人习惯，一般要么使用「离散化 + 线段树」，要么使用「线段树（动态开点）」进行求解。
本题为「非强制在线」问题，因此可以先对 ps 数组进行离散化，将值域映射到较小的空间，然后套用固定占用 $4 \times n$ 空间的线段树求解。
但更为灵活（能够同时应对强制在线问题）的求解方式是「线段树（动态开点）」。
同时实现动态开点的方式有两种：
根据操作次数对使用到的最大点数进行预估，并采用数组方式进行实现线段树（解法一）；
使用动态指针（解法二）；
方式一在不久之前的每日一题 933. 最近的请求次数 讲过，因此今天把方式二也写一下。
具体的，我们将顺序放置方块的操作（假设当前方块的左端点为 $a$，边长为 $len$，则有右端点为 $b = a + len$），分成如下两步进行：
查询当前范围 $[a, b]$ 的最大高度为多少，假设为 $cur$；
更新当前范围 $[a, b]$ 的最新高度为 $cur + len$。
因此这本质上是一个「区间修改 + 区间查询」的问题，我们需要实现带「懒标记」的线段树，从而确保在进行「区间修改」时复杂度仍为 $O(\log{n})$。
另外有一个需要注意的细节是：不同方块之间的边缘可以重合，但不会导致方块叠加，因此我们当我们对一个区间 $[a, b]$ 进行操作（查询或插入）时，可以将其调整为 $[a, b - 1]$，从而解决边缘叠加操作高度错误的问题。
线段树（动态开点 - 估点）
估点的基本方式在前置 ? 求解常见「值域爆炸，查询有限」区间问题的几种方式 详细讲过。
简单来说，可以直接估算为 $6 \times m \times \log{n}$ 即可，其中 $m$ 为询问次数（对应本题就是 ps 的长度），而 $n$ 为值域大小（对应本题可直接取成 $1e9$）；而另外一个比较实用（避免估算）的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（不考虑字节对齐，或者结构体过大的情况，Java 的 $128M$ 可以开到 $5 \times 10^6$ 以上）。
代码：
class Solution { class Node { // ls 和 rs 分别代表当前区间的左右子节点所在 tr 数组中的下标 // val 代表当前区间的最大高度，add 为懒标记 int ls, rs, val, add; } int N = (int)1e9, cnt = 0; Node[] tr = new Node[1000010]; void update(int u, int lc, int rc, int l, int r, int v) { if (l <= lc && rc <= r) { tr[u].val = v; tr[u].add = v; return ; } pushdown(u); int mid = lc + rc >> 1; if (l <= mid) update(tr[u].ls, lc, mid, l, r, v); if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v); pushup(u); } int query(int u, int lc, int rc, int l, int r) { if (l <= lc && rc <= r) return tr[u].val; pushdown(u); int mid = lc + rc >> 1, ans = 0; if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r); if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r)); return ans; } void pushdown(int u) { if (tr[u] == null) tr[u] = new Node(); if (tr[u].ls == 0) { tr[u].ls = ++cnt; tr[tr[u].ls] = new Node(); } if (tr[u].rs == 0) { tr[u].rs = ++cnt; tr[tr[u].rs] = new Node(); } if (tr[u].add == 0) return ; int add = tr[u].add; tr[tr[u].ls].add = add; tr[tr[u].rs].add = add; tr[tr[u].ls].val = add; tr[tr[u].rs].val = add; tr[u].add = 0; } void pushup(int u) { tr[u].val = Math.max(tr[tr[u].ls].val, tr[tr[u].rs].val); } public List<Integer> fallingSquares(int[][] ps) { List<Integer> ans = new ArrayList<>(); tr[1] = new Node(); for (int[] info : ps) { int x = info[0], h = info[1], cur = query(1, 1, N, x, x + h - 1); update(1, 1, N, x, x + h - 1, cur + h); ans.add(tr[1].val); } return ans; }} 时间复杂度：令 $m$ 为查询次数，$n$ 为值域大小，复杂度为 $O(m\log{n})$
空间复杂度：$O(m\log{n})$
线段树（动态开点 - 动态指针）
利用「动态指针」实现的「动态开点」可以有效避免数组估点问题，更重要的是可以有效避免 new 大数组的初始化开销，对于 LC 这种还跟你算所有样例总时长的 OJ 来说，在不考虑 static 优化/全局数组优化 的情况下，动态指针的方式要比估点的方式来得好。
代码：
class Solution { int N = (int)1e9; class Node { // ls 和 rs 分别代表当前区间的左右子节点 Node ls, rs; // val 代表当前区间的最大高度，add 为懒标记 int val, add; } Node root = new Node(); void update(Node node, int lc, int rc, int l, int r, int v) { if (l <= lc && rc <= r) { node.add = v; node.val = v; return ; } pushdown(node); int mid = lc + rc >> 1; if (l <= mid) update(node.ls, lc, mid, l, r, v); if (r > mid) update(node.rs, mid + 1, rc, l, r, v); pushup(node); } int query(Node node, int lc, int rc, int l, int r) { if (l <= lc && rc <= r) return node.val; pushdown(node); int mid = lc + rc >> 1, ans = 0; if (l <= mid) ans = query(node.ls, lc, mid, l, r); if (r > mid) ans = Math.max(ans, query(node.rs, mid + 1, rc, l, r)); return ans; } void pushdown(Node node) { if (node.ls == null) node.ls = new Node(); if (node.rs == null) node.rs = new Node(); if (node.add == 0) return ; node.ls.add = node.add; node.rs.add = node.add; node.ls.val = node.add; node.rs.val = node.add; node.add = 0; } void pushup(Node node) { node.val = Math.max(node.ls.val, node.rs.val); } public List<Integer> fallingSquares(int[][] ps) { List<Integer> ans = new ArrayList<>(); for (int[] info : ps) { int x = info[0], h = info[1], cur = query(root, 0, N, x, x + h - 1); update(root, 0, N, x, x + h - 1, cur + h); ans.add(root.val); } return ans; }} 时间复杂度：令 $m$ 为查询次数，$n$ 为值域大小，复杂度为 $O(m\log{n})$
空间复杂度：$O(m\log{n})$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.699 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
原文：https://juejin.cn/post/7102072293844582407