MLE80分求助

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
// #define int long long
const int maxn=1000010;
int a[maxn],n,b[maxn],rt[maxn],y[maxn];
class DSU{
private:
    int fa[maxn];
public:
    int find_root(int u){return fa[u]==0||fa[u]==u?u:fa[u]=find_root(fa[u]);}
    void merge(int u,int v){u=find_root(u),v=find_root(v);if(u!=v) fa[u]=v;}
}dsu;
class Leftist_Tree{
private:
    struct node{int ch[2],z,dis,sz,gs;}t[maxn];
    int top[maxn];
    void merge(int&x,int y){
        if(x==0||y==0) return t[x+y].dis=(bool)(x=x+y),void();
        if(t[x].z<t[y].z) swap(x,y);
        merge(t[x].ch[1],y);
        if(t[t[x].ch[0]].dis<t[t[x].ch[1]].dis) swap(t[x].ch[0],t[x].ch[1]);
        t[x].dis=t[t[x].ch[1]].dis+1;
    }
    int erase(int u){merge(t[u].ch[0],t[u].ch[1]);return t[u].ch[0];}
public:
    void work(){
        int lt=1;
        for(int i=1;i<=n;i++) t[i].gs=t[i].sz=1,t[i].z=a[i],rt[i]=i,top[i]=i;
        vector<int>vt;vt.push_back(rt[1]);
        for(int i=2;i<=n;i++){
            while(!vt.empty()&&t[rt[i]].z<t[vt.back()].z){
                int d=vt.back();vt.pop_back();
                dsu.merge(rt[i],d);
                int xsz=t[rt[i]].sz+t[d].sz,xg=t[rt[i]].gs+t[d].gs;
                merge(rt[i],d);
                while(xg>(xsz+1)/2) rt[i]=erase(rt[i]),xg--;
                t[rt[i]].gs=xg,t[rt[i]].sz=xsz;
            }
            top[dsu.find_root(rt[i])]=rt[i];
            vt.push_back(rt[i]);
        }
        long long ans=0;
        for(int i=1;i<=n;i++) ans+=(int)abs(a[i]-(b[i]=t[top[dsu.find_root(i)]].z));
        write(ans);write('\n');
        for(int i=1;i<=n;i++,write("\n")) write(b[i]+i);
    }
}t;
signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]-=i;
    t.work();
    return 0;
}