CF1220F Gardener Alex 题解--zhengjun

发现根节点一定是 \(1\)，所以考虑两边的子树深度，然后发现只需要考虑一段后缀或前缀的深度即可。

所以循环位移后，可以从中间往两边构建笛卡尔树，实时维护深度即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10;
int n,a[N],ans[N];
int top,stk[N],f[N];
int main(){
	scanf("%d",&n);
	if(n==1)return puts("1 0"),0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int cur=min_element(a+1,a+1+n)-a;
	rotate(a+1,a+cur,a+1+n);
	for(int i=1,x=0;i<=n;i++){
		int now=0;
		for(;top&&a[stk[top]]>a[i];top--)now=max(now+1,f[stk[top]]);
		stk[++top]=i,f[i]=now+1,x=max(x,top+now);
		ans[(cur-(n-i+1)+n)%n]=x;
	}
	rotate(a+1,a+2,a+1+n);
	memset(f,0,sizeof f);
	for(int i=n,x=top=0;i>=1;i--){
		int now=0;
		for(;top&&a[stk[top]]>a[i];top--)now=max(now+1,f[stk[top]]);
		stk[++top]=i,f[i]=now+1,x=max(x,top+now);
		int id=(cur-(n-i+1)+n)%n;
		ans[id]=max(ans[id],x);
	}
	int id=min_element(ans,ans+n)-ans;
	cout<<ans[id]<<' '<<id;
	return 0;
}