左偏树的大难题。。
只能逼自己看论文咯，我有什么办法啊
这个的话，我建议可以看ppt，感觉ppt比word那个稍微好一点点。。至少有图
然后就没什么了。。
哦，还有一个常用的技巧，看代码吧，有注释
#include<cstdio>
#include<cstring>
typedef long long LL;
#define swap(x,y) {int tt=x;x=y;y=tt;}
const int N=1000005;
int n;
int a[N];
int cnt;
int v[N];
int size[N];
int l[N],r[N],d[N];
int tot[N];
int L[N],R[N];
int root[N];
int bt (int x)
{v[++cnt]=x;size[cnt]=1;l[cnt]=r[cnt]=d[cnt]=0;return cnt;
}
int Merge (int x,int y)//维护大根堆
{if (x==0||y==0) return x+y;if (v[x]<v[y]) swap(x,y);r[x]=Merge(r[x],y);size[x]=size[r[x]]+size[l[x]]+1;if (d[r[x]]>d[l[x]]) swap(l[x],r[x]);d[x]=d[r[x]]+1;return x;
}
int abs (int x)
{return x<0?-x:x;
}
int main()
{int now=0;memset(d,0,sizeof(d));d[0]=-1;cnt=0;scanf("%d",&n);for (int u=1;u<=n;u++) {
scanf("%d",&a[u]);a[u]=a[u]-u;}//常用技巧减去i 使得最后的小于变为小于等于 这样子才可以合并 for (int u=1;u<=n;u++){now++;root[now]=bt(a[u]);tot[now]=1;L[now]=R[now]=u;while (now>1&&v[root[now-1]]>v[root[now]]){now--;root[now]=Merge(root[now],root[now+1]);tot[now]+=tot[now+1];R[now]=R[now+1];while (size[root[now]]*2>tot[now]+1)root[now]=Merge(l[root[now]],r[root[now]]);}}LL ans=0;for (int u=1;u<=now;u++)for (int i=L[u];i<=R[u];i++)ans=ans+abs(v[root[u]]-a[i]);printf("%lld\n",ans);return 0;
}