[HNOI2016] 序列 - 洛谷 P3246
看到第一眼就可以想到莫队，事实也确实如此。
假设现在的区间是 \([l, r - 1]\)，要移动到 \([l, r]\)，只需要管 \(r' = r, l \le l' \le r\) 的区间即可。
显然对于不同的 \(l'\)，最小的值会被分成若干段，而最后一段的最小值就是 \(a_r\)。所以使用单调栈求出 \(a_r\) 前面第一个比 \(a_r\) 大的位置 \(p\)，那么有贡献 \((r - p)a_r\)，然后令 \(r = p\) 继续求解即可（不妨设后面递归到的位置 \(r_i\)，对应 \(p_i\)）。
如果 \(l = 1\)，那么直接递归到最后即可，使用递推轻松解决（\(f_r = f_p + (r - p)a_r\)）。问题使可能某个 \(p_i < r_i\)，然后这一段被分为两节。我们只要找到这个 \(r_i\)，那么答案就是 \(f_r - f_{r_i} + a_{r_i}(r_i - l + 1)\)。
其实这个 \(r_i\) 也好很好找，由 \(p_i < r_i\) 可知：\(a_{r_i}\) 是 $a_{l \sim a_{r_i}} $ 中最小的；又因为这个递归中 \(a_{r_i}\) 不断减小。所以 \(a_{r_i}\) 其实就是 \([l, r]\) 中的最小值，使用 ST 表查询，然后就做完了。
时间复杂度：\(O(n \sqrt n)\)。
根据这个莫队做法，实际上可以继续推出更优秀的做法。
设最小值的位置为 \(x\)，那么对于 \(l' \le x \le r'\) 的最小值为 \(a_x\)，贡献为 \((x - l + 1)(r - x + 1)a_x\)。
对于 \(x < l'\) 的情况，由莫队算法可知，最后一定会递归到一个 \(r_i = x\)，那么贡献是 \(\sum f_{r'} - f_x = (\sum\limits_{r' = x}^r f_{r'}) - (r - x + 1)f_x\)，对于 \(r' < x\) 的情况是同理的。
时间复杂度：\(O(n \log n)\)。
先考虑通过莫队固定 \(r = r'\)，简化问题求解。然后再放开限制，分类讨论，转化为简单情况即可。（从简单到困难）