Codeforces1220F Gardener Alex

Description

有一个 (1 o n) 的排列，按照这个序列建二叉树：

(1.) 找最小的元素作为根

(2.) 排列被分为：这个元素的左边和右边两个部分

(3.) 左边最小元素成为左子节点，右边最小元素成为右子节点。

现在这个排列可以任意地向左旋转元素（(1,2,3,4 o 2,3,4,1)）

输出树的最小深度，及需要向左旋转多少的元素才能到达这个深度

Solution

断环成链

单调栈处理完控制区间，每次以当前点为儿子的含义就是左右段深度 (+1)

那么如果求一棵树的深度就是覆盖完了找所有点的被覆盖次数的最大值

那么维护一棵线段树，先更新掉 (1 o n) 的，然后逐次更新 (n+1 o 2n) 的覆盖

每次正好还把原来的覆盖了的还原掉

每次查一下最大值即可

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }
    const int N=4e5+10;
    int a[N],n;
    int mx[N<<2],tag[N<<2];
    inline void push_down(int p)
    {
        if(!tag[p]) return ;
        tag[p<<1]+=tag[p]; tag[p<<1|1]+=tag[p];
        mx[p<<1]+=tag[p]; mx[p<<1|1]+=tag[p];
        tag[p]=0;
        return ;
    }
    inline void push_up(int p){return mx[p]=max(mx[p<<1],mx[p<<1|1]),void();}
    inline int query(int p,int l,int r,int st,int ed)
    {
        if(st<=l&&r<=ed) return mx[p];
        int mid=(l+r)>>1,res=0; push_down(p);
        if(st<=mid) res=max(res,query(p<<1,l,mid,st,ed));
        if(ed>mid) res=max(res,query(p<<1|1,mid+1,r,st,ed)); 
        return res;
    }
    inline void upd(int p,int l,int r,int st,int ed,int v)
    {
        if(st<=l&&r<=ed) return tag[p]+=v,mx[p]+=v,void();
        
        int mid=(l+r)>>1; push_down(p);
        if(st<=mid) upd(p<<1,l,mid,st,ed,v);
        if(ed>mid) upd(p<<1|1,mid+1,r,st,ed,v);
        return push_up(p),void();
    }
    int l[N],r[N],st[N],top;
    signed main()
    {
        n=read(); 
        for(reg int i=1;i<=n;++i) a[i]=read(),a[i+n]=a[i];
        n<<=1; st[++top]=0; 
        for(reg int i=1;i<=n;++i) 
        {
            while(a[st[top]]>=a[i]) r[st[top]]=i-1,top--;
            st[++top]=i;
        }
        while(top) r[st[top]]=n,top--;
        for(reg int i=n;i>=1;--i) 
        {
            while(a[st[top]]>=a[i]) l[st[top]]=i+1,top--;
            st[++top]=i;
        }
        while(top) l[st[top]]=1,top--;
        for(reg int i=1;i<=n/2;++i) upd(1,1,n,l[i],r[i],1);
        int ans=query(1,1,n,1,n/2),mn=0;
        for(reg int i=1;i<n/2;++i) 
        {
            upd(1,1,n,l[i],r[i],-1);
            upd(1,1,n,l[i+n/2],r[i+n/2],1);
            int res=query(1,1,n,i+1,i+n/2);
            if(res<ans){ans=res,mn=i;}
        } cout<<ans<<" "<<mn<<endl;
        return 0;
    }
}
signed main(){return yspm::main();}