E题题解

思路

为什么要数据随机？因为不随机做不出来。

考虑这么一个例子，

1 2 3 4 5 6 7 8 9 ...

我们要取出所有的区间，复杂度是 $O(n^2)$ 的，直接爆炸。

现考虑随机性。

我们固定左端点，右端点在不断右移的时候，能够使得区间改变 $max, min$ 的位置是有限的。

为什么？

改变 $max$ 需要严格大于，每次选出一个大于其的数，后续严格大于的期望其实是在不断折半的，因此最多 $log$ 个。同理对于 $min$ ，所以我们固定左端点，右端点有效移动的位置，是这些严格大于/小于的位置之和，最多 $2log$ 个，我们通过单调栈 + 双指针即可完成模拟。

通过单调栈找严格大于/小于，然后通过双指针取出这些位置， $map$ 记录 $val = max \times min$ 的数量，最后丢进数组中，记录 $suf$ 即可。