M_sea的博客

M_sea的博客

A Mengbier

题解 CF1156E 【Special Segments of Permutation】

posted on 2019-05-04 22:02:03 | under 题解 |

枚举+单调栈。

先预处理出每个 $i$ 左边第一个大于它的位置(记为 $L[i]$ )和右边第一个大于它的位置(记为 $R[i]$ )。显然可以单调栈 $O(n)$ 求出。

枚举最大值的位置,那么左端点只会落在 $(L[i],i)$ ,右端点只会落在 $(i,R[i])$ 。

那么在小的那个区间中枚举一个端点,在另外那个区间中查有没有对应的值。

这样子看上去是 $O(n^2)$ 的,实际上是 $O(n\log n)$ 的。具体证明戳这里

代码