「Bzoj 1660」「Usaco2006 Nov」Bad Hair Day 乱发节 (单调栈)

BZOJ 1660
Luogu 2866
from: USACO 2006 Nov Sliver(USACO刷题第6题)

单调栈,对于每个数,他后面所有比他小的数(中间不能有大于他的数)都会对答案做出贡献。
那么我们可以用单调栈来维护这个”后面所有比他小的数(中间不能有大于他的数)”

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 80000 + 5;
int n, hi[MAXN], top, stk[MAXN];
void clear() {
top = 0;
}
void init() {
clear();
for (int i=1;i<=n;i++) scanf("%d", &hi[i]);
}
void solve() {
LL ans = 0;
for (int i=1;i<=n;i++) {
if (hi[i]<stk[top]) {
ans += top;
} else {
while (top&&hi[i]>=stk[top]) top--;
ans += top;
}
stk[++top] = hi[i];
}
printf("%lld\n", ans);
}
int main() {
while (scanf("%d", &n)==1&&n) init(), solve();
return 0;
}

------ 本文结束 ------