ansv.cpp

// Linear time all nearest smaller values, standard stack-based algorithm.
// ansv_left stores indices of nearest smaller values to the left in res. -1 means no smaller value was found.
// ansv_right likewise looks to the right. v.size() means no smaller value was found.
void ansv_left(vector<int>& v, vector<int>& res) {
	stack<pair<int, int> > stk; stk.push(make_pair(INT_MIN, v.size()));
	for (int i = v.size()-1; i >= 0; i--) {
		while (stk.top().first > v[i]) {
			res[stk.top().second] = i; stk.pop();
		}
		stk.push(make_pair(v[i], i));
	}
	while (stk.top().second < v.size()) {
		res[stk.top().second] = -1; stk.pop();
	}
}

void ansv_right(vector<int>& v, vector<int>& res) {
	stack<pair<int, int> > stk; stk.push(make_pair(INT_MIN, -1));
	for (int i = 0; i < v.size(); i++) {
		while (stk.top().first > v[i]) {
			res[stk.top().second] = i; stk.pop();
		}
		stk.push(make_pair(v[i], i));
	}
	while (stk.top().second > -1) {
		res[stk.top().second] = v.size(); stk.pop();
	}
}