请求卡常数

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 8e5+5;

int n,op,a[N];

struct fenwick {
    int bit[N];
    void init(){
        memset(bit,0,sizeof bit);
    }
    inline void M(int p,int v=1){
        while (p<N){
            bit[p]+=v,p+=p&-p;
        }
    }
    inline int Q(int p){
        if (p<0) return 0;
        int res=0;
        while (p){
            res+=bit[p],p-=p&-p;
        }
        return res;
    }
} t;

struct Sub1 {
    int ans[N],ls[N],tot;
    int gt(int x){
        return lower_bound(ls+1,ls+1+tot,x)-ls;
    }
    void solve(){
        t.init();
        for (int i=1; i<=n; i++) ans[i]=0;
        for (int i=1; i<=n; i++){
            ls[++tot]=a[i]-i;
        }
        sort(ls+1,ls+1+tot);
        tot=unique(ls+1,ls+1+tot)-ls-1;
        for (int i=1; i<=n; i++){
            ans[i]+=t.Q(gt(a[i]-i)-1);
            t.M(gt(a[i]-i));
        }
        tot=0,t.init();
        for (int i=1; i<=n; i++){
            ls[++tot]=a[i]+i;
        }
        sort(ls+1,ls+1+tot);
        tot=unique(ls+1,ls+1+tot)-ls-1;
        for (int i=n; i; i--){
            ans[i]+=t.Q(gt(a[i]+i)-1);
            t.M(gt(a[i]+i));
        }
        for (int i=1; i<=n; i++){
            cout<<ans[i]+1<<"\n";
        }
    }
} s1;

struct Sub2 {
    int ans[N],ls[N],tot,b[N];
    int gt(int x){
        return lower_bound(ls+1,ls+1+tot,x)-ls;
    }
    void cal(int x){
        tot=0,t.init();
        for (int i=1; i<=n; i++){
            b[i]=a[i]+abs(i-x);
            ls[++tot]=b[i];
        }
        sort(ls+1,ls+1+tot);
        tot=unique(ls+1,ls+1+tot)-ls-1;
        for (int i=1; i<=n; i++){
            t.M(gt(b[i]),1);
        }
        for (int i=1; i<=n; i++){
            ans[i]=max(ans[i],t.Q(gt(b[i])-1));
        }
    }
    int cur[N];
    void sol(){
        for (int i=1; i<=n; i++) cur[i]=0;
        t.init(),tot=0;
        // 外面
        for (int i=1; i<=n; i++){
            ls[++tot]=a[i];
            ls[++tot]=a[i]+i-1;
        }
        sort(ls+1,ls+1+tot);
        tot=unique(ls+1,ls+1+tot)-ls-1;
        for (int i=1; i<=n; i++){
            t.M(gt(a[i]),1);
        }
        cur[1]+=t.Q(gt(a[1])-1);
        t.M(gt(a[2]),-1);
        for (int i=2,j=3; i<=n; i++,j+=2){
            cur[i]+=t.Q(gt(a[i]+i-1)-1);
            if (j<=n) t.M(gt(a[j]),-1);
            if (j+1<=n) t.M(gt(a[j+1]),-1);
        }
        // 左边
        t.init(),tot=0;
        for (int i=1; i<=n; i++){
            ls[++tot]=a[i]+i;
        }
        sort(ls+1,ls+1+tot);
        tot=unique(ls+1,ls+1+tot)-ls-1;
        for (int i=2; i<=n; i++){
            cur[i]+=t.Q(gt(a[i]+i)-1);
            t.M(gt(a[i]+i));
        }
        // 右边
        t.init(),tot=0;
        for (int i=1; i<=n; i++){
            ls[++tot]=a[i]-i;
        }
        sort(ls+1,ls+1+tot);
        tot=unique(ls+1,ls+1+tot)-ls-1;
        for (int i=n,j=n; i>1; i--){
            while (j>=2*i-1){
                t.M(gt(a[j]-j),-1);
                j--;
            }
            cur[i]+=t.Q(gt(a[i]-i)-1);
            t.M(gt(a[i]-i));
        }
        // max
        for (int i=1; 2*i-1<=n; i++){
            ans[i]=max(ans[i],cur[i]);
        }
    }
    void solve(){
        cal(1),cal(n);
        sol();
        reverse(a+1,a+1+n);
        reverse(ans+1,ans+1+n);
        sol();
        reverse(ans+1,ans+1+n);
        for (int i=1; i<=n; i++){
            cout<<ans[i]+1<<"\n";
        }
    }
} s2;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    freopen("marathon.in","r",stdin);
    freopen("marathon.out","w",stdout);
    cin>>n>>op;
    for (int i=1; i<=n; i++){
        cin>>a[i];
    }
    if (op==1){
        s1.solve();
    }
    else{
        s2.solve();
    }
    return 0;
}