记初始序列为$a_{i}$，答案序列为$b_{i}$（显然唯一），考虑如何求出$b_{i}$
引理1：$b_{i}$具有凸性（下凸）
考虑反证，若$b_{i}$不具有凸性，即存在$2b_{i}>b_{i-1}+b_{i+1}$，那么操作$(i-1,i,i+1)$也即可使得$b_{x}$减小，与最小性矛盾
引理2：$\forall p\in \Z,\min_{1\le i\le n}(a_{i}-pi)=\min_{1\le i\le n}(b_{i}-pi)$
考虑对$(i,j,k)$的操作，由最小性显然$a'_{j}\le a_{j}$，即该式单调不增
另一方面，显然有$\min(a_{i}-pi,a_{k}-pk)\le a'_{j}-pj$，即该式单调不减
综上，该式的值不因操作而变化，即得证
结论：记$c_{p}=\min_{1\le i\le n}(a_{i}-pi)$，则$\forall 1\le i\le n,b_{i}=\max_{p\in \Z}(c_{p}+pi)$
由引理2，显然$b_{i}-pi\ge c_{p}$，因此左式$\ge $右式
由引理1，取$p\in [b_{i}-b_{i-1},b_{i+1}-b_{i}]$，显然$b_{i}-pi$取到最小值，再结合引理2可得$b_{i}-i=c_{p}$，因此左式$\le $右式
综上，即得证
考虑$px+c_{p}$这条直线，假设$c_{p}$在$i_{0}$处取到最小值，代入即求经过$(i_{0},a_{i_{0}})$斜率为$p$的直线，那么再对每一个点$(i,a_{i})$找到最小和最大的$p$（使得$c_{p}$在其上取最小值），最后将所有直线求一个（上）凸包即可
关于每一个点的$p$，显然也即对所有点求（下）凸包，其中每一个点上一段斜率上取整和下一段的斜率下取整（其余点均不存在满足条件的$p$）
时间复杂度为$o(n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 300005 4 #define ll long long 5 struct Point{ 6 ll x,y; 7 }P[N]; 8 struct Line{ 9 ll k,b; 10 }Q[N<<1]; 11 int n,m,st[N<<1]; 12 ll ans; 13 double get_k(Point x,Point y){ 14 return 1.0*(x.y-y.y)/(x.x-y.x); 15 } 16 double get_x(Line x,Line y){ 17 return -1.0*(x.b-y.b)/(x.k-y.k); 18 } 19 int main(){ 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++){ 22 scanf("%lld",&P[i].y); 23 P[i].x=i; 24 } 25 for(int i=1;i<=n;i++){ 26 while ((st[0]>1)&&(get_k(P[st[st[0]-1]],P[st[st[0]]])>=get_k(P[st[st[0]]],P[i])))st[0]--; 27 st[++st[0]]=i; 28 } 29 for(int i=1;i<=st[0];i++){ 30 ll k1=-1e18,k2=1e18; 31 if (i>1)k1=ceil(get_k(P[st[i-1]],P[st[i]])); 32 if (i<st[0])k2=floor(get_k(P[st[i]],P[st[i+1]])); 33 if (k1>k2)continue; 34 if ((i>1)&&((!m)||(Q[m].k<k1)))Q[++m]=Line{k1,P[st[i]].y-k1*P[st[i]].x}; 35 if ((i<st[0])&&((!m)||(Q[m].k<k2)))Q[++m]=Line{k2,P[st[i]].y-k2*P[st[i]].x}; 36 } 37 st[0]=0; 38 for(int i=1;i<=m;i++){ 39 while ((st[0]>1)&&(get_x(Q[st[st[0]-1]],Q[st[st[0]]])>=get_x(Q[st[st[0]]],Q[i])))st[0]--; 40 st[++st[0]]=i; 41 } 42 for(int i=1,j=1;i<=n;i++){ 43 while ((j<st[0])&&(get_x(Q[st[j]],Q[st[j+1]])<i))j++; 44 ans+=Q[st[j]].k*i+Q[st[j]].b; 45 } 46 printf("%lld\n",ans); 47 return 0; 48 }