题目链接

题解

又是一道神题，，

我们考虑一些简单的情况：

我们先假设\(b_i\)单调不降，而不是递增

对于递增序列\(\{a_i\}\)，显然答案\(\{b_i\}\)满足\(b_i = a_i\)

对于递减序列\(\{a_i\}\)，显然答案\(\{b_i\}\)满足\(b_i\)为\(a_i\)的中位数

于是我们有了初步的想法：

将\(a_i\)分成若干个单调递减的段，每段的答案为其中位数

然后顺次访问段

如果两段的答案是递增的，显然这两段就没有影响，相互独立了，就保留答案

如果相邻两段的答案是递减的，就合并这两段，重新寻找它们的中位数

~~可以证明是对的~~

对于单调递增的处理，我们只需令\(A[i] = A[i] - i\)，即可转变为单调不下降

维护中位数可以用对顶堆实现，由于涉及堆的合并，那就使用左偏树

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
          
           (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
           
            #define LL long long intusing namespace std;const int maxn = 1000005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int val[maxn],ls[maxn],rs[maxn],d[maxn],siz[maxn],rt[maxn],Rt[maxn];int merge(int a,int b){ if (!b) return a; if (!a) return b; if (val[b] < val[a]) swap(a,b); rs[a] = merge(rs[a],b); siz[a] = siz[ls[a]] + 1 + siz[rs[a]]; if (d[ls[a]] < d[rs[a]]) swap(ls[a],rs[a]); d[a] = rs[a] ? d[rs[a]] + 1 : 0; return a;}int Merge(int a,int b){ if (!b) return a; if (!a) return b; if (val[b] > val[a]) swap(a,b); rs[a] = Merge(rs[a],b); siz[a] = siz[ls[a]] + 1 + siz[rs[a]]; if (d[ls[a]] < d[rs[a]]) swap(ls[a],rs[a]); d[a] = d[rs[a]] + 1; return a;}int n,pos[maxn],len[maxn],K;LL A[maxn];void work(){ int tmp; d[0] = -1; for (int i = 1; i <= n; i++){ pos[++K] = i; len[K] = 1; rt[i] = i; siz[rt[i]] = 1; val[i] = A[i]; while (K > 1 && val[rt[pos[K]]] < val[rt[pos[K - 1]]]){ K--; rt[pos[K]] = merge(rt[pos[K]],rt[pos[K + 1]]); Rt[pos[K]] = Merge(Rt[pos[K]],Rt[pos[K + 1]]); len[K] += len[K + 1]; while (siz[rt[pos[K]]] > siz[Rt[pos[K]]]){ tmp = rt[pos[K]]; rt[pos[K]] = merge(ls[rt[pos[K]]],rs[rt[pos[K]]]); ls[tmp] = rs[tmp] = 0; siz[tmp] = 1; Rt[pos[K]] = Merge(Rt[pos[K]],tmp); } while (siz[rt[pos[K]]] < siz[Rt[pos[K]]]){ tmp = Rt[pos[K]]; Rt[pos[K]] = Merge(ls[Rt[pos[K]]],rs[Rt[pos[K]]]); ls[tmp] = rs[tmp] = 0; siz[tmp] = 1; rt[pos[K]] = merge(rt[pos[K]],tmp); } } //printf("[%d,%d] mid = %d\n",i - len[K] + 1,i,val[rt[pos[K]]]); } LL ans = 0,v; for (int i = 1,l = 1; i <= K; i++){ v = siz[rt[pos[i]]] > siz[Rt[pos[i]]] ? val[rt[pos[i]]] : val[Rt[pos[i]]]; //printf("[%d,%d] v = %lld\n",l,l + len[i] - 1,v); for (int j = 0; j < len[i]; j++) ans += abs(v - A[l + j]); l += len[i]; } printf("%lld\n",ans);}int main(){ n = read(); REP(i,n) A[i] = read() - i; //REP(i,n) printf("%lld ",A[i]); puts(""); work(); return 0;}