问题描述 : 在无限长的数轴（即 x 轴）上，我们根据给定的顺序放置对应的正方形方块。 第 i 个掉落的方块（positions[i] = (left, side_length)）是正方形，其中 left 表示该方块最左边的点位置(positions[i][0])，side_length 表示该方块的边长(positions[i][1])。 每个方块的底部边缘平行于数轴（即 x 轴），并且从一个比目前所有的落地方块更高的高度掉落而下。在上一个方块结束掉落，并保持静止后，才开始掉落新方块。 方块的底边具有非常大的粘性，并将保持固定在它们所接触的任何长度表面上（无论是数轴还是其他方块）。邻接掉落的边不会过早地粘合在一起，因为只有底边才具有粘性。 返回一个堆叠高度列表 ans 。每一个堆叠高度 ans[i] 表示在通过 positions[0], positions[1], …, positions[i] 表示的方块掉落结束后，目前所有已经落稳的方块堆叠的最高高度。
示例 1: 输入: [[1, 2], [2, 3], [6, 1]] 输出: [2, 5, 5] 解释: 第一个方块 positions[0] = [1, 2] 掉落： _aa _aa
方块最大高度为 2 。
图中，a表示被方块占住的区域，a前面的下划线表示空白区域。
第二个方块 positions[1] = [2, 3] 掉落：
__aaa
__aaa
__aaa
aa_
aa_
方块最大高度为5。
大的方块保持在较小的方块的顶部，不论它的重心在哪里，因为方块的底部边缘有非常大的粘性。
第三个方块 positions[1] = [6, 1] 掉落：
__aaa
__aaa
__aaa
_aa
_aa___a 方块最大高度为5。 因此，我们返回结果[2, 5, 5]。
示例 2: 输入: [[100, 100], [200, 100]] 输出: [100, 100] 解释: 相邻的方块不会过早地卡住，只有它们的底部边缘才能粘在表面上。
输入说明 : 首先输入方块的数目n 然后输入n行，每行两个整数，表示方块的left和side_length 1 <= n <= 1000. 1 <= left <= 10^8. 1 <= side_length <= 10^6.
输出说明 : 输出结果，共n个整数， 第i个整数表示前i个方块堆叠的高度。 整数之间以空格分隔。
输入范例 : 3 1 2 2 3 6 1
输出范例 : 2 5 5
#include<iostream> #include<vector> #include<map> #include<set> using namespace std; class Solution { public: map<int, int>mp; set<int>st; set<int>str; const int MX = 2009; int mx[4 * 2009]; #define lson (rt<<1) #define rson (rt<<1|1) #define gmid (l+r>>1) void pushup2(int rt){ mx[rt] = max(mx[rson], mx[lson]); return; } void update2(int L, int R, int l, int r, int rt, int val){ if (l == r){ mx[rt] = val; return; } int mid = gmid; if (L <= mid)update2(L, R, l, mid, lson, val); if(R>mid) update2(L, R, mid + 1, r, rson, val); pushup2(rt); } int query2(int L, int R, int l, int r, int rt){ if (L <= l && r <= R) return mx[rt]; int mid = gmid; int res = 0; if (L <= mid)res = max(res, query2(L, R, l, mid, lson)); if (R > mid)res = max(res, query2(L, R, mid + 1, r, rson)); return res; } vector<int> fallingSquares(vector<vector<int>>& positions) { int sz = positions.size(); for (int i = 0; i < sz; i++){ mp[positions[i][0]] = 1; mp[positions[i][0] + positions[i][1]-1] = 1; } int cnt = 1; for (auto&it : mp){ it.second = cnt++; } int lef, rig; int tp; vector<int>res; for (int i = 0; i < sz; i++){ lef = mp[positions[i][0]]; rig = mp[positions[i][0]+ positions[i][1]-1]; tp = query2(lef, rig, 1, 2009, 1); update2(lef, rig, 1, 2009, 1, tp + positions[i][1]); res.push_back(mx[1]); } return res; } }; int main(){ int n; cin>>n; int x,y; vector<vector<int>> positions; vector<int> tmp; for(int i=0;i<n;i++){ cin>>x; cin>>y; tmp.push_back(x); tmp.push_back(y); positions.push_back(tmp); tmp.clear(); } vector<int> res=Solution().fallingSquares(positions); for(int i=0;i<n;i++){ cout<<res[i]; if(i!=n-1){ cout<<" "; } } }