【单调栈】乱头发节

题意： 一头牛头向左看，高的能看见低的牛的头发，问你，所有牛能看见的头发的总量是多少？

分析： 向左看，如果看到了比自己高的牛，那么这头牛就会挡住视线，反之就能看过去，如果被挡住视线的话，后续的牛就与他没有关系了，那就可以走了。

既然遇到更高的就没有贡献了，意思是如果要使得有贡献，那么有贡献的就是单调的，而要使得目前还能去看的牛有贡献，那么当前被看的牛就不会挡住去看他的牛，意思是被看的牛的身高小于去看的牛的身高 -> 单调减栈

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12;
int a[N],n,mx[N][20],mn[N];
int rmq(int l,int r)
{
  int k=r-l+1;
  if( a[mx[l][mn[k]]] > a[mx[r-(1<<mn[k])+1][mn[k]]] ) return mx[l][mn[k]];
  else return mx[r-(1<<mn[k])+1][mn[k]];
  //if (  mx[l][mn[k]]==l and a[mx[l][mn[k]]] > a[mx[r-(1<<mn[k])+1][mn[k]]] ) return 1 ;
  //return 0;
}
int main(){
  //freopen("std.in","r",stdin);
  //freopen("std.out","w",stdout);
  cin>>n;
  long long ans=0;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    mx[i][0]=i;
  }
  for(int i=2;i<=n;i++)
  {
    mn[i]= i&(i-1) ? mn[i-1] : mn[i-1]+1;
  }
  for(int j=1; (1<<j)-1<=n ; j++ )
  {
    for(int i=1;i+(1<<j)-1<=n;i++)
    {
      if(  a[mx[i+(1<<j-1)][j-1]]>=a[ mx[i][j-1] ]  )
      mx[i][j]=mx[i+(1<<j-1)][j-1];
      else mx[i][j]=mx[i][j-1];
    }
  }
  //cout<<endl;
  for(int i=1;i<=n-1;i++)
  {
    int l=i,r=n;
    while(l<=r)
    {
      int mid=l+r>>1;
      if( rmq(i,mid)==i ) l=mid+1;
      else r=mid-1;
    }
    ans+=l-1-i;
    //cout<<ans<<endl;
  }
  cout<<ans;
}