POJ-3250 : Bad Hair Day

問題概要

長さn(<8*10^4)の数列xが与えられる(x[n]=infとする)。各iについて(min j s.t. i

解法

All nearest smaller valuesという有名問題。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

typedef long long int64;

const int MAX_N = 80000;

int N;
int hs[MAX_N], nxtLarger[MAX_N];

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", hs + i);
	}
}

int64 solve() {
	vector<int> stack;
	stack.reserve(N);

	for (int i = N - 1 ; i >= 0; --i) {
		for (;!stack.empty() && hs[stack.back()] < hs[i]; stack.pop_back()) ;
		nxtLarger[i] = stack.empty() ? N : stack.back();
		stack.push_back(i);
	}

	int64 ans = 0;
	for (int i = 0; i < N; ++i) {
		ans += (nxtLarger[i] - i - 1);
	}
	return ans;
}

int main() {
	init();
	printf("%lld\n", solve());

	return 0;
}