bzoj 1660: [Usaco2006 Nov]Bad Hair Day 乱发节【单调栈】

开一个单调递减的单调栈，然后用sum数组维护每个点的答案，新加点的时候一边退栈一边把退掉的点的sum加进来

#include<iostream>

#include<cstdio>

using namespace std;

const int N=800005;

int s[N],top,a[N],n,sum[N];

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

int main()

{

    n=read();

    for(int i=1;i<=n;i++)

		a[i]=read();

    for(int i=n;i>=1;i--)

    {

        while(top&&a[i]>a[s[top]])

			sum[i]+=sum[s[top--]]+1;

        s[++top]=i;

    }

	long long ans=0;

    for(int i=1;i<=n;i++)

		ans+=sum[i];

    printf("%lld\n",ans);

}

巴特西

bzoj 1660: [Usaco2006 Nov]Bad Hair Day 乱发节【单调栈】

最新文章

热门文章