﻿ bzoj 1367 [ Baltic 2004 ] sequence —— 左偏树

### bzoj 1367 [ Baltic 2004 ] sequence —— 左偏树

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=1e6+5;
int n,t[maxn],l[maxn],r[maxn],rt[maxn],siz[maxn],num[maxn];
int ls[maxn],rs[maxn],dis[maxn];
ll ans;
int abb(int x){return x>0?x:-x;}
int merge(int x,int y)
{
if(!x||!y)return x+y;
if(t[x]<t[y])swap(x,y);//维护大根堆
rs[x]=merge(rs[x],y);
siz[x]=siz[ls[x]]+siz[rs[x]]+1;//+1
if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);
if(rs[x])dis[x]=dis[rs[x]]+1;
else dis[x]=0;
return x;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&t[i]),t[i]-=i;
int nw=0;
for(int i=1;i<=n;i++)
{
l[++nw]=r[nw]=i; rt[nw]=i;
siz[rt[nw]]=num[nw]=1;
while(nw>1&&t[rt[nw-1]]>t[rt[nw]])
{
nw--;
num[nw]+=num[nw+1]; r[nw]=r[nw+1];
rt[nw]=merge(rt[nw],rt[nw+1]);
while(siz[rt[nw]]*2>num[nw]+1)//+1
rt[nw]=merge(ls[rt[nw]],rs[rt[nw]]);
}
}
for(int i=1;i<=nw;i++)
for(int j=l[i];j<=r[i];j++)ans+=abb(t[j]-t[rt[i]]);
printf("%lld
",ans);
return 0;
}```