- 题意：给定一个h序列，对于\(h_i\)，找到一个\(j\)满足\(j < i\)且\(h_j >= h_i\)，令\(ans_i = h_i * (i - j + 1) + ans_j + 1\)，最后输出ans序列。
- 赛时给了个很魔怔的解法，不知道是不是正解，反正是过了（摊手）
- 我们可以开一个idx数组，将h[i]从小到大排序后将其原下表存入idx数组，这样我们从前到后遍历，就能保证前面存入的下标对应的h一定大于当前的h。这样我们维护一棵平衡树，树中存idx，对于idx[i]，我们只需要找到其在平衡树中的前驱，即为这个idx[i]对应的满足上面条件的下表j，之后就有
ans[idx[i]] = ans[j] + (idx[i] - j) * h[idx[i]] + 1。由于j已经被存入平衡树，所以我们可以保证ans[j]一定存在。 - 很魔怔，但是好用（再次摊手）