1220F - Gardener Alex（笛卡尔树）

original link - http://codeforces.com/problemset/problem/1220/F

题意：

对出一个序列，你可以对其循环左移，问循环左移几次后，这个序列构造出的笛卡尔树层数最少。

解析：

我们可以先拎起最小的点，那么左边$x$，右边$n-1-x$。一边的长度为$i$的树可以从长度为$i-1$的树得到。所以就是一边维护笛卡尔树，一边记录答案。

用$dp$记录每个点左儿子的最深层数，假设新进入一个没有左儿子的点，层数就是当前栈的大小。如果有左儿子，那么$dp=max(d{p}_{son}+1)$。

代码：

/*
 *  Author : Jk_Chen
 *    Date : 2019-09-20-11.05.10
 */
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<x<<'\n';
const LL mod=1e9+7;
const int maxn=2e5+9;
LL rd(){ LL ans=0; char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans; return ans;
}
/*_________________________________________________________begin*/

int tmp[maxn];
int a[maxn];
int sta[maxn],top,val[maxn];

int dpl[maxn],dpr[maxn];

void init(int n,int *dp){
    top=0;
    int mx=0;
    rep(i,1,n){
        int ma=0;
        while(top&&a[sta[top]]>a[i]){
            ma=max(ma,val[top]);
            top--;
        }
        sta[++top]=i;
        if(ma==0){
            val[top]=top;
        }
        else{
            val[top]=ma+1;
        }
        dp[i]=(mx=max(mx,val[top]));
    }
}


int main(){
    int n=rd();
    if(n==1)return 0*printf("%d %d\n",1,0);
    int mi=1e9,rt;
    rep(i,1,n){
        tmp[i]=rd();
        if(tmp[i]<mi)mi=tmp[i],rt=i;
    }
    for(int i=1,j=rt-1;i<n;i++,j--){
        if(j<1)j+=n;
        a[i]=tmp[j];
    }
    init(n-1,dpl);
    for(int i=1,j=rt+1;i<n;i++,j++){
        if(j>n)j-=n;
        a[i]=tmp[j];
    }
    init(n-1,dpr);
    int ans=1e9,__;
    rep(i,0,n-1){
        if(ans>1+max(dpl[i],dpr[n-1-i])){
            ans=1+max(dpl[i],dpr[n-1-i]);
            __=rt-(i+1);
        }
    }
    if(__<0)__+=n;
    printf("%d %d\n",ans,__);
}