比如，你来到8，已知8的右边最小值是5，如下 …8…5… 你就知道，5这个数是一定要增长到8才行的。5 -> 8，增长3次。 我们用线段树，5…7范围上，都设置成1！注意！不是+1，是线段树里update操作！不是add操作！ 表示： 所有的5肯定都要变的(线段树里5位置+1，表示关于5要操作一次) 所有的6肯定都要变的(线段树里6位置+1，表示关于6要操作一次) 所有的7肯定都要变的(线段树里7位置+1，表示关于7要操作一次) 然后，假设你接下来，来到7，7的右边最小值还是5，如下： …8 7…5… 我们用线段树，5…6范围上，都设置成1！你会发现，其实没啥变化，因为之前5…7范围都已经设置成1了。 这正好是我们要的效果！ 然后，假设你接下来，来到9，9的右边最小值还是5，如下： …8 7 9…5… 我们用线段树，5…8范围上，都设置成1！你会发现，其实只在8位置上变化了，因为之前5…7范围上，都已经设置成1了。 最后你看看线段树里，总体累加和是多少就可以了。 再举个例子： 13 6 30 19 你来到13，发现右边最小值是6，于是线段树6…12范围，都设置成1 你来到6，发现右边最小值>=6，于是线段树什么也不做。 你来到30，发现右边最小值是19，于是线段树19…29范围，都设置成1 你来到19，线段树什么也不做。 最终，线段树里，只有6…12、19…29范围上有1，所以线段树整体累加和是18。就是我们要的答案。 因为值在10^9范围，所以用开点线段树，或者，用线段树离散化处理。都可以。 最小值这个信息可以用预处理数组。 时间复杂度O(N * log N)