Discretization and ZKW segment tree(iterative segment tree)
\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        //Discretization \n        map<int,vector<int> >hash;\
```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        //Discretization \n        map<int,vector<int> >hash;\n        vector<vector<int> >pos(positions.size(),vector<int>{0,-1,-1});//pos is the discretization of positions,pos[0] is the height of positions[i], [pos[1],pos[2]] is the discrete range of positions[i]\n        for(int i=0;i<positions.size();i++){\n            pos[i][0]=positions[i].second;\n            int st=positions[i].first,en=positions[i].first+positions[i].second-1;\n            if(hash.find(st)==hash.end())hash.emplace(st,vector<int>{i});\n            else hash[st].push_back(i);\n            if(hash.find(en)==hash.end())hash.emplace(en,vector<int>{i});\n            else hash[en].push_back(i);\n        }\n        int i=0;\n        for(auto p:hash){\n            for(int j:p.second){\n                if(pos[j][1]==-1)pos[j][1]=i;\n                else pos[j][2]=i;\n            }\n            i++;\n        }\n        vector<int>res;\n        int n=pow(2,ceil(log2(hash.size()+2))),m=0,f=1;\n        vector<pair<int,int> >sgt(2*n-1,pair<int,int>(0,0));//iterative segment tree,pair.first is max height,pair.second is 'focused lazy value'(a lazy value not a mark,never push-down)\n        for(auto v:pos){\n            if(f){//first square\n                for(int i=v[1]+n;i<=v[2]+n;i++)update_single(sgt,i,v[0]);\n                f=0;m=v[0];\n                res.push_back(m);\n            }else{\n                int mt=query_range(sgt,v[1]+n,v[2]+n)+v[0];//max height in [v[1],v[2]]\n                update_range(sgt,v[1]+n,v[2]+n,mt);//update height in [v[1],v[2]] to mt\n                m=max(m,mt);\n                res.push_back(m);\n            }\n        }\n        return res;\n    }\n    void update_single(vector<pair<int,int> >&sgt,int i,int v){\n        for(;i>0;i=(i-1)/2)sgt[i].first=v;\n    }\n    int query_range(vector<pair<int,int> >&sgt,int i,int j){\n        int st=i-1,en=j+1,ml=0,mr=0,fl=0,fr=0;\n        for(;en-st>=1;st=(st-1)/2,en=(en-1)/2){\n            if(sgt[st].second&&fl)ml=max(ml,sgt[st].second);\n            if(en-st>1&&st%2){ml=max(ml,sgt[st+1].first);fl=1;}\n            if(sgt[en].second&&fr)mr=max(mr,sgt[en].second);\n            if(en-st>1&&en%2==0){mr=max(mr,sgt[en-1].first);fr=1;}\n        }        \n        ml=max(ml,mr);\n        for(;st>0;st=(st-1)/2){\n            if(sgt[st].second)ml=max(ml,sgt[st].second);\n        }\n        return ml;\n    }\n    void update_range(vector<pair<int,int> >&sgt,int i,int j,int m){\n        int st=i-1,en=j+1,fl=0,fr=0;\n        for(;en-st>=1;st=(st-1)/2,en=(en-1)/2){\n            if(st*2+1<sgt.size()&&fl)sgt[st].first=max(sgt[st*2+1].first,sgt[st*2+2].first);\n            if(en-st>1&&st%2){sgt[st+1].first=m;sgt[st+1].second=m;fl=1;}\n            if(en*2+1<sgt.size()&&fr)sgt[en].first=max(sgt[en*2+1].first,sgt[en*2+2].first);\n            if(en-st>1&&en%2==0){sgt[en-1].first=m;sgt[en-1].second=m;fr=1;}\n        }\n        for(;st>0;st=(st-1)/2){\n            sgt[st].first=max(sgt[st].first,max(sgt[st*2+1].first,sgt[st*2+2].first));\n        }        \n    }};\n```
[]