题解：P7988 [USACO21DEC] HILO G

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200001],ans[200005];
struct node {
	int ls,rs,fa,tong,sum;
} tr[200001]; //tong存优先级,sum存键值
bool cmp(node s1,node s2) {
	return s1.sum<s2.sum;
}
void build_tree() {
	stack<int> k;
	k.push(0);
	for(int i=1; i<=n; i++) {
		int pos=k.top();
		while(!k.empty()&&tr[i].tong>tr[pos].tong) { //单调栈建树
			pos=tr[pos].fa;
			k.pop();
		}
		tr[i].ls=tr[pos].rs; 
		tr[i].fa=pos;
		tr[tr[i].ls].fa=i;
		tr[pos].rs=i;
		k.push(i); 
	}
	return ;
}
void dfs(int x,int l,int r,int ans1,int y) {
	if(l==r) {
		ans[l-1]=ans1;
		return ;
	}
	if(y==1)dfs(tr[x].rs,x+1,r,ans1+1,2);
	else dfs(tr[x].rs,x+1,r,ans1,2);
	dfs(tr[x].ls,l,x,ans1,1);
	return ;
}
signed  main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		tr[i].tong=n-i+1;//记优先级
		tr[i].sum=a[i]; //记键值
	}
	sort(tr+1,tr+n+1,cmp);
	tr[0].tong=1e18;//把第0个的优先级设最大，这样用单调栈时不会出现栈空的情况
	build_tree();//建树
	int t=0;
	for(int i=1; i<=n; i++)if(tr[i].fa==0)t=i; //找根节点
	dfs(t,1,n+1,0,0);
	for(int i=0; i<=n; i++)cout<<ans[i]<<"\n";
	return 0;
}