公式解説の方法の時間計算量を評価すると \(O(N^2)\) になりますが、このユーザー解説では時間計算量 \(O(N)\) の解法を紹介します。

単調スタック (Monotonic Stack) （蟻本 p.298 で使われるテクニック）を利用した解法で、公式解説より難易度が高くなっています。

長さ \(N\) の配列 \(A = (A_1, A_2, \cdots, A_N)\) と、各 \(i = 0, 1, 2, \cdots, N\) について、次に定める列を \(C_i\) とします。直感的に、 \(C_i\) は \(i\) から左に進んだときの累積 max の更新点を記録したものです。 \(C_i\) の値は (値, index) のペアを保持するとします。

• 最初は \(x = - \infty\) であるとする。また、列 \(T\) は空列とする。
• \(j = i, i-1, \cdots, 1\) について、\(x < A_j\) ならば、 \(x\) を \(A_j\) に更新し、 \(T\) の先頭に \((A_j, j)\) を挿入する。
• \(C_i\) を最終的な列 \(T\) とする。

このとき、人 \(i\) の答えは、 \(C_i\) の末尾から 2 番目の要素 \((v, j)\) についての \(j\) （なければ \(-1\) ）となります。なぜなら、 \(C_i\) の末尾の要素は \((A_i, i)\) であり、 \(C_i\) の構成方法から \(v > A_i\) で、 \(j<k<i\) に対しては \(A_k \le A_i\) となるからです。

たとえば、 \(A = (17,10,12,7,8)\) のとき、 \(C_5 = ((17, 1), (12,3),(8,5))\) となり、人 \(5\) に対する答えは \(3\) となります。

\(C_{i-1}\) から \(C_{i}\) を得る

\(C_i\) を stack （C++ の std::vector や python の list で代用可能）として管理することを考えます。 \(C_{i-1}\) から \(C_{i}\) を得るには、

• まず、\(X=C_{i-1}\) とする。
• \(X\) が空でなく、\(X\) の末尾 \((v, j)\) について \(v \le A_{i}\) である限り \(X\) の末尾を削除 (pop) する。
• その後、 \(X\) の末尾に \((A_{i}, i)\) を追加 (push) したものを \(C_{i}\) とする。

として得られます。

人 \(i\) についての答えは、 \(X\) の末尾に \((A_{i}, i)\) を追加する前の末尾 \((v,j)\) についての \(j\) の値（なければ \(-1\)）となります。

以上のアルゴリズムを \(i=1,2,\cdots, N\) に対して行い答えをすべて求めることが可能です。計算量は全体で \(O(N)\) となります。計算量評価は特に各要素 \(A_i\) が stack に最大で 1 回 push され、最大で 1 回 pop されることから行うことができます。

実装

以下の実装では \(C_0\) は空列ではなく、 \(M\) を \(\max A\) より大きい値（今回は \(M=10^9\)）として、代わりに \(C_0 = ((M,-1))\) としています。

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	vector<int> val = {int(1e9)}; // stack の値
	vector<int> ind = {-1}; // その座標
	for (int i=0; i<n; i++) {
		while (val.back() <= a[i]) {
			val.pop_back();
			ind.pop_back();
		}
		cout << ind.back() << '\n';
		val.push_back(a[i]);
		ind.push_back(i + 1);
	}
}