代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read(){
    int ans=0,a=getchar();
    while('0'>a||a>'9')a=getchar();
    while('0'<=a&&a<='9')ans=ans*10+a-'0',a=getchar();
    return ans;
}
int r[1000005],L[21][1000005],R[21][1000005],n,N,f1[21][1000005],f2[21][1000005],lg[1000005];
void build(){
    for(int i=1;i<=N;i++)f1[0][i]=f2[0][i]=i;
    for(int len=1;len<=lg[N];len++){
        for(int i=1;i+(1<<len)-1<=N;i++){
            f1[len][i]=(L[0][f1[len-1][i]]>L[0][f1[len-1][i+(1<<len-1)]]?f1[len-1][i+(1<<len-1)]:f1[len-1][i]);
            f2[len][i]=(R[0][f2[len-1][i]]>R[0][f2[len-1][i+(1<<len-1)]]?f2[len-1][i]:f2[len-1][i+(1<<len-1)]);
        }
    }
}
inline int findL(int l,int r){
    int k=lg[r-l+1];
    return min(f1[k][l],f1[k][r-(1<<k)+1]);
}
inline int findR(int l,int r){
    int k=lg[r-l+1];
    return max(f2[k][l],f2[k][r-(1<<k)+1]);
}
inline int solve(int now){
    int ans=0,l=now,r=now;
    for(int i=lg[N];i>=0;i--){
        int ll1=findL(l,r), rr1=findR(l,r);
        int ll=min(L[i][ll1],L[i][rr1]),rr=max(R[i][ll1],R[i][rr1]);
        if(rr-ll+1<n){
            ans+=(1<<i);
            l=ll,r=rr;
        }
    }
    if(r-l+1<n)ans++;
    return ans;
}

int main(){
    n=read();
    N=3*n;
    for(int i=1;i<=n;i++){
        r[i]=r[i+n]=r[i+n+n]=read();
    }
    lg[1]=0;
    for(int i=2;i<=N;i++)lg[i]=lg[i-1]+((i&(i-1))==0);
    for(int i=1;i<=N;i++){
        L[0][i]=max(1,i-r[i]);
        R[0][i]=min(N,i+r[i]);
    }
    build();
    for(int k=1;k<=lg[N];k++){
        for(int i=1;i<=N;i++){
            int pl=findL(L[k-1][i],R[k-1][i]),pr=findR(L[k-1][i],R[k-1][i]);
            L[k][i]=min(L[k-1][pl],L[k-1][pr]);
            R[k][i]=max(R[k-1][pl],R[k-1][pr]);
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",solve(n+i));
    }
    puts("");
    return 0;
}

评测结果