题解：P14753 森

snowQAQ · 2026-07-20 07:50:53 · 题解

前置知识：单调栈，树状数组。

看到区间最小值想到单调栈拓展区间。

先找出最小值能最大扩展的左右区间 [L,R]，[L,i) 就是 l 可取的范围，(i,R] 就是 r 可取的范围。这个很好维护，用单调栈就行，然后在 l 左侧找第比 a_l 小的数的个数，在 r 右侧找到比 a_r 小的数的个数，这个很明显，两个树状数组维护就行。最后根据题目乘起来就是答案。