Baltic2014 sequence

问题描述

输入格式

输出格式

一个整数R

样例输入

7
9
4
8
20
14
15
18

样例输出

13

数据范围

所求的Z序列为6,7,8,13,14,15,18.
R=13

解析&左偏树详解

IOI2005国家集训队论文 黄源河

代码

#include <iostream>
#include <cstdio>
#define N 1000002
using namespace std;
int n,i,j,a[N],son[N][2],fa[N],dis[N],num[N],l[N],r[N],q[N],top;
long long val[N];
long long abs(long long x)
{
	return x>0?x:-x;
}
int merge(int x,int y)
{
	if(x==0) return y;
	if(y==0) return x;
	if(val[x]<val[y]||(val[x]==val[y]&&x>y)) swap(x,y);
	son[x][1]=merge(son[x][1],y);
	num[x]=num[son[x][0]]+num[son[x][1]]+1;
	if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]);
	fa[son[x][0]]=fa[son[x][1]]=fa[x]=x;
	dis[x]=dis[son[x][1]]+1;
	return x;
}
void pop(int x)
{
	fa[son[x][0]]=son[x][0];
	fa[son[x][1]]=son[x][1];
	fa[x]=merge(son[x][0],son[x][1]);
}
int main()
{
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>val[i];
		val[i]-=i;
		a[i]=val[i];
	}
	val[0]=-1;
	for(i=1;i<=n;i++){
		q[++top]=i;
		l[top]=r[top]=i;
		num[i]=1;
		while(top>1&&val[q[top-1]]>val[q[top]]){
			q[top-1]=merge(q[top-1],q[top]);
			top--;
			r[top]=i;
			while(num[q[top]]>(r[top]-l[top]+2)/2) pop(q[top]),q[top]=fa[q[top]];
		}
	}
	long long ans=0;
	for(i=1;i<=top;i++){
		for(j=l[i];j<=r[i];j++){
			ans+=abs(a[j]-val[q[i]]);
		}
	}
	cout<<ans<<endl;
	return 0;
}