单调栈-向右寻找比自己大的第一个数

单调栈

向右寻找比自己大的第一个数
poj 3250 Bad Hair Day

#include<iostream>
#include<cstdio>
#include<stack>
#define M 80100
#define ll long long
using namespace std;
ll a[M];
int L[M];
stack<ll>s;
int main( )
{
      int n;
      cin>>n;
      for(int i=1;i<=n;i++)
      {
            cin>>a[i];
      }
      for(int i=n;i>=1;i--)
      {
            while(!s.empty( )&&a[s.top( )]<a[i])
            {
                  s.pop( );
            }
            if(s.empty( ))
            {
                  L[i]=n+1;
            }
            else
            {
                  L[i]=s.top( );
            }
            s.push(i);
      }
      /*for(int i=1;i<=n;i++)
      {
            cout<<L[i]<<" ";
      }
      cout<<endl;*/
      ll ans=0;
      for(int i=1;i<=n;i++)
      {
            ans+=(L[i]-i-1);
      }
      cout<<ans<<endl;
      return 0;
}