BZOJ1660: [Usaco2006 Nov]Bad Hair Day 乱发节(单调栈)

题意

Sol

单调栈板子题。。

找到向左第一个比他大的位置，然后判断一下就可以了

#include<bits/stdc++.h>

//#define int long long

#define LL long long

using namespace std;

const int MAXN = 1e6 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, a[MAXN], st[MAXN], top;

signed main() {

    N = read();

    for(int i = 1; i <= N; i++) a[i] = read();

    reverse(a + 1, a + N + 1);

    LL ans = 0;

    for(int i = 1; i <= N; i++) {

        while(top && a[i] > a[st[top]]) top--;

        ans += i - st[top] - 1;

        st[++top] = i;

    }

    cout << ans;

    return 0;

}

/*

5

5 5 5 5 5

*/

巴特西

BZOJ1660: [Usaco2006 Nov]Bad Hair Day 乱发节(单调栈)

题意

Sol

最新文章

热门文章