出处： Educational Codeforces Round 152
链接： https://codeforces.com/problemset/problem/1849/E
题目大意：
TODO（先去看原题吧）
解题思路：
PS：这里的解题思路跟标准答案不太一样，是用数据结构硬怼的（分治 + 双指针 + 数据结构加速（ST表 + 笛卡尔树）），不是那种优雅巧妙的CF解法，更像是丑陋的区域赛解法。
- 第一步，从数据量猜复杂度。这里要统计有多少个子数组，其最大值的位置在最小值的右侧。题目的数据量非常大（1e6），属于是硬卡 \(O(n^2)\) 的典范，不过实测优化得比较好的 \(O(n\cdot log^2n) = O(n\cdot logn \cdot logn)\) 也可以通过，可能是出题人的仁慈吧，但实际运行起来还是慢得不行。
- 这个问题看起来很像是一种分治算法，我在比赛中曾经构思过一种跨越中点的分治算法，好像不太成功，因为要分最大值和最小值分别处于不同的区间进行非常多次数的讨论。但按区间中点分治的算法可以保证复杂度。
- 这种类型（区间的最大值、最小值的管辖范围）的题目关联的数据结构一般是单调栈或者笛卡尔树，从笛卡尔树可以得到启发，考虑使用最大值进行分治，就只需要每次讨论最小值的位置，然后直接递归给左右子树，以此循环。
- 从上面的想法可以大概可以得出一个分治的框架：
ll calc (int L, int R) { // 计算[L, R]区间内有多少个满足条件的子数组
if (L >= R) { // 递归到叶子节点，平凡的退出条件
return 0;
}
if (L == R - 1) { // 递归到近似叶子节点，平凡的退出条件
return a[R] > a[L];
}
int M = maxValPos; // 通过某种手段得到最大值的位置，作为递归左右子树的分割点M
ll sum = 0;
sum += calc (L, M - 1);
sum += calc (M + 1, R);
// do some calc! 计算跨越分割点M的答案，由于跨越了最大值a[M]，所以最大值一定是a[M]
return sum;
}
这里大功告成一半了，然后就要想 do some calc 里面做什么。
- 由于这里不是按照区间的中点进行分治，在极端的情形（左右子树分配不均匀，比如近似单调上升或者近似单调下降的序列）下，会导致线性复杂度（\(O(R-L+1)\)）的 do some calc 让整个算法变成平方级。但是这种问题先忽略吧，先看看是不是能用线性复杂度去做这个问题？
- 这里由于确定了最大值的位置一定是M，满足题目要求的条件的最小值必须出现在[L, M-1]之中，那么有个简单的思路就是从M-1开始一个一个枚举子区间的左端点l，一直枚举到L，然后对于其中的每一个l，可以通过 \(O(1)\) 维护一个前缀的最小值minValue，然后从区间的右边[M, R]之中选出尽可能远的子区间右端点r（注意这里是可以取值为M的），使得[M, r]之中不存在一个更小的值minValue。然后统计[M, r]之中一共有多少个选择，记得排除掉长度为1的区间的情况。这个双指针算法是比较明显的，应该接近1900分的水平就随便想到了。
- 然后想一想这个算法有没有可以优化的地方？其实单独这个双指针算法的话确实是线性复杂度就是最优了，但是这里是为了解决分治的时候左右子树不平衡的问题，所以可以想一想是不是可以只对左右子树里面短的那一侧使用线性复杂度的算法，另一侧用数据结构加速。
- 刚刚举的例子其实是枚举左端点l，进而确定最小值minValue，然后通过某种方式计算右端点r的最远选择位置。这里的话问题转化成“在一个数组上找一个尽可能靠右的点，使得起点到它之间的最小值大于minValue”，注意到前缀min其实是单调的，所以这里一定可以二分，然后用一个数据结构支持快速查询区间最小值就可以了，这个数据结构自然是ST表。
- 然后再想一想枚举右端点的情况，枚举右端点的时候是能确定右侧的最小值minValue2，然后在左区间找一个尽可能靠右的点，使得从这个点开始到区间中点的后缀最小值minValue小于minValue2。容易发现这个也是个ST表二分可以做的东西。那这道题就差不多做完了。
- 不过还遗留了最后一个问题，就是如何确定区间中最大值的位置呢？这个ST自然也可以维护（用pair就可以，first存值，second存位置；或者对于这道题来说可以用一个值映射位置的数组就可以）。但是实际上交上去之后会MLE掉，毕竟ST表是个空间换时间的神奇玩意，自然出题人不会希望多用。
- 再想一想，ST表其实使用多余的空间来提供O(1)的任意区间最值查询的功能，但本算法的最大值的选取规则是仿照笛卡尔树的，那么笛卡尔树本身就可以取出最大值，用 \(O(n)\) 的时空复杂度就可以了。
从这一题可以看出积累的科技越多，用奇奇怪怪的算法组合出的东西就越奇怪，甚至会偏离出题人想教会你的某种独特的计数方法，用classical的方式强行解决这个问题。这也是数据结构的魅力8。作为队伍里的数据结构选手，思维被局限在这种依靠科技的奇技淫巧上了。或许应该去做atcoder。