Breaking 2D into 1D Problem || Step by Step Lazy Propogation and Coordinate Compression
\n# Approach\nInstead of thinking of squares as $2-D$ figures, we can treat them as a line segment flattened into a $1-D$ plane holding a value which is equal t
\n# Approach\nInstead of thinking of squares as $2-D$ figures, we can treat them as a line segment flattened into a $1-D$ plane holding a value which is equal to the side of the sqaure. *[See below image.]*\n![image.png](https://assets.leetcode.com/users/images/8e6b5353-17d6-4465-ae5a-c07cc46eef48_1732276148.0156393.png)\n\n\nIn order to make computations easier a square can be represented as two line segments covering **S =** ***(x[0], x[0]+x[1]-1)***. \n\nSo the problem is now converted to an easier familiar problem of assigning a value of *x[1]* to the range **S** and finding the maximum in the entire range from ***[1, max(x[0]+x[1])]***. This can be easily done via **Lazy Segment Tree**.\n\nBut there is one problem, since the coordinates can be of the order of *1e8*, storing them directly would lead to *memory limit exceed*. \n\nWe can ask ourselves: does the volume of the starting and ending points of range really matters? \nThe answer is no, it does not. What matters is the relative ordering of ranges, For this we can utilize a technique called **Coordinate Compression**. \n\nBy compressing the coordinates we can easily fit the points to a memory friendly limit.\n\nFor more info about Lazy Segment Tree: https://codeforces.com/edu/course/2/lesson/5/2\nFor more info about Coordinate Compression: https://usaco.guide/silver/sorting-custom\n\n\n# Complexity\n- Time complexity:\n$O(NlogN)$\n\n- Space complexity:\n$O(N)$\n\n# Code\n```cpp []\nstruct segTree {\n    vector<long long> tr, op;\n    int size;\n    const long long NO_OPERATION = LLONG_MAX;  \n    const long long NULL_VALUE = 0;   \n\n    segTree(int n) {\n        size = 1;\n        while (size < n) size *= 2;\n        tr.assign(size * 2, 0);\n        op.assign(size * 2, NO_OPERATION);\n    }\n\n    long long calc_op(long long a, long long b) {\n        return max(a, b);\n    }\n\n    long long modify_op(long long a, long long b, long long len) {\n        return (b == NO_OPERATION) ? a : b;\n    }\n\n    void apply_op(long long &a, long long b, long long len) {\n        a = modify_op(a, b, len);\n    }\n\n    void propagate(int v, int lx, int rx) {\n        if (op[v] == NO_OPERATION || rx - lx == 1) return;\n        int m = (lx + rx) / 2;\n        apply_op(tr[2 * v + 1], op[v], m - lx);\n        apply_op(op[2 * v + 1], op[v], 1);\n        apply_op(tr[2 * v + 2], op[v], rx - m);\n        apply_op(op[2 * v + 2], op[v], 1);\n        op[v] = NO_OPERATION;\n    }\n\n    void build(int v, int lx, int rx, const vector<long long> &a) {\n        if (rx - lx == 1) {\n            if (lx < (int)a.size()) {\n                tr[v] = a[lx];\n            }\n            return;\n        }\n        int m = (lx + rx) / 2;\n        build(2 * v + 1, lx, m, a);\n        build(2 * v + 2, m, rx, a);\n        tr[v] = calc_op(tr[2 * v + 1], tr[2 * v + 2]);\n    }\n\n    void build(const vector<long long> &a) {\n        build(0, 0, size, a);\n    }\n\n    void modify(int v, int lx, int rx, int l, int r, long long val) {\n        propagate(v, lx, rx);\n        if (rx <= l || lx >= r) return;\n        if (lx >= l && rx <= r) {\n            apply_op(tr[v], val, rx - lx);\n            apply_op(op[v], val, 1);\n            return;\n        }\n        int m = (lx + rx) / 2;\n        modify(2 * v + 1, lx, m, l, r, val);\n        modify(2 * v + 2, m, rx, l, r, val);\n        tr[v] = calc_op(tr[2 * v + 1], tr[2 * v + 2]);\n    }\n\n    void modify(int l, int r, long long val) {\n        modify(0, 0, size, l, r, val);\n    }\n\n    long long calc(int v, int lx, int rx, int l, int r) {\n        propagate(v, lx, rx);\n        if (rx <= l || lx >= r) return NULL_VALUE;\n        if (lx >= l && rx <= r) return tr[v];\n        int m = (lx + rx) / 2;\n        long long s1 = calc(2 * v + 1, lx, m, l, r);\n        long long s2 = calc(2 * v + 2, m, rx, l, r);\n        return calc_op(s1, s2);\n    }\n\n    long long calc(int l, int r) {\n        return calc(0, 0, size, l, r);\n    }\n};\nclass Solution {\npublic:\n   \n    vector<int> fallingSquares(vector<vector<int>>& positions) {\n        set<int> cord;\n        for(auto &x: positions) {\n            cord.insert(x[0]);\n            cord.insert(x[0]+x[1]);\n        }\n        int id = 0;\n        map<int, int> compress;\n        for(auto x: cord) compress[x]=id++;\n        segTree seg(id);\n        vector<int> res;\n        int mx = 0;\n        for(auto &x: positions) {\n            int l = compress[x[0]], r = compress[x[0]+x[1]]; \n            int cur = seg.calc(l, r);\n            seg.modify(l, r, cur+x[1]);\n            res.push_back(seg.calc(0, id));\n        }\n        return res;\n    }\n};\n```
['Hash Table', 'Segment Tree', 'Ordered Set', 'C++']