✅✅Easy Readable c++ code || Segment Tree with lazy propagation || Cordinate Compression.
Intuition and Approach\n Describe your first thoughts on how to solve this problem. \nFirst of all, it will feel awkard and you might not get the intution of se
# Intuition and Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst of all, it will feel awkard and you might not get the intution of segment tree. But when you deminish 2D concept into 1D by replacing the height by values at in 1D. Then you will get idea of segment tree.\n\nFor a time being, forgot about cordinate compression. That is easiest part of this problem.\n\nThis figure in testcase-1  will diminish to:\n![1.jpeg](https://assets.leetcode.com/users/images/cc7d05d9-2a26-43db-8383-7a00b0109c1a_1687180203.5096328.jpeg)\n\nNow think it as range update and range query. Whenever a new square comes, it gets stacked and freezed over tallest stack in its range [l,r]. Just imagine like tetris game. Have you digested till now? If not, please use pen paper and visualize.\n\nso, what will be flow to solve the problem:\n    For each query:\n       1.Query maximum height in range of upcoming square.\n       2.Update the value of all element in this range by \n`updatedVal=height of coming square+ maximum value earlier in that range.`\n       3. Then again query for maximum height in overall range [1,n].\n\n\nSo,let\'s know how to implement it:\nuse lazy propagation over segment tree for this.You can read it over [here.](https://cp-algorithms.com/data_structures/segment_tree.html#range-updates-lazy-propagation)\n\nUnder the topic given above in link, you will have two subsection:\n1. Addtion over segment/range [concentrate over why we mark lazy[0] after pushing for the node]\n2. Assignment over segment/range. [we will use this].\n    since i am not using marked vector to track assignment (just to save space), i will use the fact that our height will never be -1, so i will just make lazy[node]=-1 after pushing/assignment for the node and whenever lazy[node]==-1, i will not update my node.\n```\nvoid push(int node)\n{\n    if(lazy[node]!=-1)\n    {\n       tree[2*node] =tree[2*node+1]=lazy[node];\n       lazy[2*node] = lazy[2*node+1]=lazy[node];\n       lazy[node]=-1;\n    }\n}\n```\n\nAfter that, it is as same as normal code for lazy propagation.\n\n**But you will ask, cordinates are order of 1e8**, so this will not work. So, use cordinate compression for that. Since ,maximum positions can be no more that 2*size of given vector,so we will only need some critical x cordinates.\n```\n      unordered_map<int, int> index;\n      set<int> sortedCoords;\n      for (const auto& pos : positions) \n      {\n          sortedCoords.insert(pos[0]);\n          sortedCoords.insert(pos[0] + pos[1] - 1);\n      }\n      int compressedIdx = 1;\n      for (auto it:sortedCoords) \n      {\n          index[it] = compressedIdx;\n          compressedIdx++;\n      }  \n\n```\n![2.jpeg](https://assets.leetcode.com/users/images/02233b02-6ea3-43c9-87dc-431c645c54e6_1687181859.9336245.jpeg)\n\n\nNaming of variables are as:\n- tl and tr are range of positions denoted by tree[node].\n- l and r are our given range of query.\n\nNote: I am using 1-based indexing in the following implementation.\n\n# Complexity\n- Time complexity: O(m * log(n)) where n= last compressed index and m=number of queries. As , we are using 2 query and 1 update per query.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1e5) as i am using a constant size tree and lazy.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    const static int N = 1e5 + 2;\nint INF = 1e9;\nint tree[4 * N], lazy[4 * N];\nvoid push(int node)\n{\n    if(lazy[node]!=-1)\n    {\n       tree[2*node] =tree[2*node+1]=lazy[node];\n       lazy[2*node] = lazy[2*node+1]=lazy[node];\n       lazy[node]=-1;\n    }\n}\nvoid update(int node, int tl, int tr, int l, int r, int updatedVal)\n{\n    if (tl > tr)return;\n    else if (l<=tl && tr <=r)\n    {\n        tree[node] = updatedVal;\n        lazy[node] = updatedVal; // ye value update krni hai tl to tr segment of segment tree.\n    }\n    else if(tl==tr && (tl<l||tr>r)) return;\n    else\n    {\n        push(node);\n        int tm = (tl + tr) / 2;\n        update(2*node, tl, tm, l,r, updatedVal);\n        update(2*node + 1, tm + 1, tr,l, r, updatedVal);\n        tree[node] = max(tree[2*node], tree[2*node+ 1]);\n    }\n}\nint query(int node, int tl, int tr, int l, int r)\n{\n    if (tl >tr)return -INF;\n    if (l <= tl && tr <= r)return tree[node];\n    if(tl==tr) return -INF;\n    push(node);\n    int tm = (tl + tr) / 2;\n    int q1=query(2*node, tl, tm, l,r);\n    int q2=query(2*node + 1, tm + 1, tr,l, r);\n    return max(q1,q2);\n}\n\n vector<int> fallingSquares(vector<vector<int>>& positions) \n  {\n      memset(tree,0,sizeof(tree));\n      memset(lazy,0,sizeof(lazy));\n      memset(a,0,sizeof(a));\n\n      unordered_map<int, int> index;\n      set<int> sortedCoords;\n      for (const auto& pos : positions) \n      {\n          sortedCoords.insert(pos[0]);\n          sortedCoords.insert(pos[0] + pos[1] - 1);\n      }\n      int compressedIdx = 1;\n      for (auto it:sortedCoords) \n      {\n          index[it] = compressedIdx;\n          compressedIdx++;\n      }  \n      int n= compressedIdx;\n      int best = 0;\n      vector<int> ans;  \n      for (const auto& pos : positions) \n      {\n          int l = index[pos[0]];\n          int r = index[pos[0] + pos[1] - 1];\n          int mxinlr=query(1,1,n,l,r);\n          update(1,1,n,l,r,mxinlr+pos[1]);\n          int temp=query(1,1,n,1,n);\n          ans.push_back(temp);\n      }\n      return ans;\n  }\n};\n```
['Segment Tree', 'C++']