【BZOJ1367】[Baltic2004]sequence 左偏树

【BZOJ1367】[Baltic2004]sequence

Description

Input

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

13

HINT

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

题解：详见论文

然而本题要求z[i]严格递增，那就让所有t[i]-=i就好了

#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;

}