我看到有人在做单调栈。

机房同学说：诶，这东西非得单调栈做吗？

我说是这道题吗？（另一道）好像用点 log 数据结构也行。

他认为这个板子就能直接做。

我按他的想法打了代码。

#include<bits/stdc++.h>
using namespace std;
int a[3000010],dp[3000010];
int slv(int x,int id){
	if (id==0) return 0;
	else if (a[id]>x) return id; 
	else return slv(x,dp[id]);
}
int main(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	dp[n]=0;
	for (int i=n-1;i>=1;i--){
		dp[i]=slv(a[i],i+1);
	}
	for (int i=1;i<=n;i++) cout<<dp[i]<<' ';
	return 0;
}

然后过了这题。

他认为这是均摊，总体 $O(n)$ 的。