在二维平面上的 x 轴上，放置着一些方块。
给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。
在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。
示例 1：
输入：positions = [[1,2],[2,3],[6,1]] 输出：[2,5,5] 解释： 第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。 第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。 第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。 因此，返回 [2, 5, 5] 作为答案。
示例 2：
输入：positions = [[100,100],[200,100]] 输出：[100,100] 解释： 第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。 第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。 因此，返回 [100, 100] 作为答案。 注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。
提示：
·1 <= positions.length <= 1000
·1 <= lefti <= 108
·1 <= sideLengthi <= 106
题目大意：计算每个方块着陆后所有方块堆叠的最大高度。
分析：
（1）可以用数组height[i]记录坐标i上的方块的最高高度。则放置一个新方块position[i]，只需将坐标position[i][0]到坐标(position[i][0]+position[i][1]-1)中所有坐标的高度全置为这些坐标中的最大高度+position[i][1]，在遍历方块的过程中再维护所有方块的最高高度即可得出每个方块着陆后所有方块堆叠的最大高度；
（2）由于题目中坐标的个数较多，用height数组记录所有坐标的高度时间复杂度和空间复杂度较大，但记录所有坐标的高度是冗余的，只需记录每个方块的起始坐标position[i][0]和终止坐标(position[i][0]+position[i][1]-1)上的高度即可；
（3）根据（2）再开辟一个数组site[i]记录每个方块的起始位置和终止位置，并对site数组排序和去重，height[i]便用于记录坐标site[i]的高度。为更新坐标position[i][0]到坐标(position[i][0]+position[i][1]-1)中所有坐标的高度，只需在site中用二分查找position[i][0]的下标k，然后从height[k]开始往后更新到height[p]，其中site[p]=position[i][0]+position[i][1]-1。
class Solution {
public:
int findSite(vector<int>& site,int M,int tar){
int l=0,r=M-1,mid;
while(l<=r){
mid=(l+r)/2;
if(site[mid]==tar) return mid;
else if(site[mid]>tar) r=mid-1;
else l=mid+1;
}
return -1;
}
vector<int> fallingSquares(vector<vector<int>>& positions) {
int N=positions.size(),maxH=0;
vector<int> site;
site.reserve(2*N);
for(const auto& v:positions){
site.emplace_back(v[0]);
site.emplace_back(v[0]+v[1]-1);
}
sort(site.begin(),site.end());
site.erase(unique(site.begin(),site.end()),site.end());
int M=site.size();
vector<int> height(M,0),ans(N);
for(int i=0,start,end,len,tmp;i<N;++i){
len=positions[i][1];
start=findSite(site,M,positions[i][0]);
end=positions[i][0]+len-1;
tmp=0;
for(int j=start;j<M&&site[j]<=end;++j) tmp=max(tmp,height[j]);
tmp+=len;
for(int j=start;j<M&&site[j]<=end;++j) height[j]=tmp;
maxH=max(tmp,maxH);
ans[i]=maxH;
}
return ans;
}
};