分治+笛卡尔树碎碎念原题(codeforces) 赛时这题wa了。赛后看到d题大多题解都是栈啊什么的，我没看懂，最终看到一个跟我思路完全相同的一个题解，检查发现没有特判如下的情况（其实是画蛇添足），魂都被气飞了。 1211 新人第一发题解wa了，第二发求过（ 题解 首先观察整个数列 定义 是最小值的下标。显然你不能删除最小值，并且删除 左侧和 右侧的元素是独立事件。因此答案就是 和 答案的乘积。 那么如何处理一般化的数列 呢？显然我们只有两种选择：保留 （ 中最小值的下标），或者使用 或 （如果它们存在）来删除 。 定义 ， 分别是 和 的答案。不论何时，我们可以有 种方法来保留 。如果 , 我们有 种方法来删除 。如果 , 我们有 种方法来删除 。如果 且 , 我们重复计算了删除 中所有元素的情况，因此我们需要再减去 。 原本我使用 min_element 求最小值，经群 u 提醒（指直接上手 hack ）构造单调序列可以 tle ，因此我们需要预处理一个笛卡尔树。 原文 by TheScrasse Solve the problem ...