【BZOJ1367】[Baltic2004]sequence

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn=1000010;int v[maxn];int l[maxn],r[maxn],rt[maxn],nvl[maxn],ch[maxn][2];int n,m;int merge(int x,int y){	if(!x)	return y;	if(!y)	return x;	if(v[x]<v[y])	swap(x,y);	ch[x][1]=merge(ch[x][1],y);	if(nvl[ch[x][0]]<nvl[ch[x][1]])	swap(ch[x][0],ch[x][1]);	nvl[x]=nvl[ch[x][1]]+1;	return x;}long long ans;long long z(int a){	return (long long)(a>0?a:-a);}int main(){	scanf("%d",&n);	int i,j;	for(i=1;i<=n;i++)	scanf("%d",&v[i]),v[i]-=i;	for(i=1;i<=n;i++)	{		l[++m]=r[m]=rt[m]=i;		while(v[rt[m]]<v[rt[m-1]]&&m>1)		{			rt[m-1]=merge(rt[m-1],rt[m]);			for(j=1;j<=(r[m-1]-l[m-1]+1)/2+1+(r[m]-l[m]+1)/2+1-(r[m]-l[m-1]+1)/2-1;j++)	rt[m-1]=merge(ch[rt[m-1]][0],ch[rt[m-1]][1]);			r[m-1]=r[m],m--;		}	}	for(i=1;i<=m;i++)		for(j=l[i];j<=r[i];j++)			ans+=z(v[rt[i]]-v[j]);	printf("%lld",ans);	return 0;}