单调栈模板题

这道题很明显就是让你求最长的向右的都比她小的连续区间长度（不能有中断）。

遇到这种问题我们可以使用单调栈，能够在\(O(n)\)的时间内求出来。

这是我模拟一下单调栈工作的机制：

可以发现，我们维护的单调栈具有上升的单调性，每次入栈一个新元素就把比她小的元素都搞掉。

其实也不难发现：每个元素在单调栈的存活时间就是他们能看到的连续区间长度了。

况且这道题\(n\)挺小的，直接用STL水过。

代码：

#include
    
     #include
     
      #include
      
       #define ll long longconst int maxn = 80005;std::stack
       
        
          > sta;int a[maxn];int n;ll ans;int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++)    {        scanf("%d", &a[i]);        while(!sta.empty() && sta.top().first <= a[i])        {            ans += i - sta.top().second - 1;            sta.pop();        }        sta.push(std::make_pair(a[i], i));    }    while(!sta.empty())    {        ans += n - sta.top().second;        sta.pop();    }    printf("%lld\n", ans);    return 0;}