C# Dynamic Segment Tree (Online search) Beats 100%
Code\n\npublic class Solution {\n    public class Node{\n        public int l, r, cnt, add;\n        public Node(int l, int r, int cnt, int add){\n            t
# Code\n```\npublic class Solution {\n    public class Node{\n        public int l, r, cnt, add;\n        public Node(int l, int r, int cnt, int add){\n            this.l = l;\n            this.r = r;\n            this.cnt = cnt;\n            this.add = add;\n        }\n    }\n\n    const int N = (int)1e9 + 7, M = 100010;\n    Node[] tr = new Node[M * 4];\n    int pos = 1;\n    public IList<int> FallingSquares(int[][] positions) {\n        List<int> list = new();\n        for(int i = 0; i < positions.Length; i++){\n            int x = positions[i][0], len = positions[i][1];\n            int res = Query(1, 1, N - 1, x, x + len - 1);\n            Update(1, 1, N - 1 , x, x + len - 1, res + len);\n            list.Add(Query(1, 1, N - 1, 1, N - 1));\n        }\n        return list.ToArray();\n    }\n\n    public void PushUp(int u){\n        tr[u].cnt = Math.Max(tr[tr[u].l].cnt, tr[tr[u].r].cnt);\n    }\n\n    public void PushDown(int u){\n        if(tr[u] == null) tr[u] = new Node(0, 0, 0, 0);\n        if(tr[u].l == 0){\n            tr[u].l = ++pos;\n            tr[tr[u].l] = new Node(0, 0, 0, 0);\n        }\n        if(tr[u].r == 0){\n            tr[u].r = ++pos;\n            tr[tr[u].r] = new Node(0, 0, 0, 0);\n        }\n        if(tr[u].add == 0) return;\n\n        tr[tr[u].l].add = tr[u].add;\n        tr[tr[u].r].add = tr[u].add;\n\n        tr[tr[u].l].cnt = tr[u].add;\n        tr[tr[u].r].cnt = tr[u].add;\n        tr[u].add = 0;\n    }\n\n    public void Update(int u, int lc, int rc, int l, int r, int d){\n        if(l <= lc && rc <= r){\n            tr[u].cnt = d;\n            tr[u].add = d;\n            return;\n        }\n        int mid = rc + lc >> 1;\n        PushDown(u);\n        if(l <= mid) Update(tr[u].l, lc, mid, l, r, d);\n        if(r > mid) Update(tr[u].r, mid + 1, rc, l, r, d);\n        PushUp(u);\n    }\n\n    public int Query(int u, int lc, int rc, int l, int r){\n        if(l <= lc && rc <= r) return tr[u].cnt;\n        int max = 0;\n        PushDown(u);\n        int mid = rc + lc >> 1;\n        if(l <= mid) max = Query(tr[u].l, lc, mid, l, r);\n        if(r > mid) max = Math.Max(max, Query(tr[u].r, mid + 1, rc, l, r));\n        return max;\n    }\n}\n```
['C#']