bzoj1588[HNOI2002]營業額統計

bzoj1588[HNOI2002]營業額統計

Description

營業額統計 Tiger最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計並分析公司成立以來的營業情況。 Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當復雜的工作。由於節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況： 該天的最小波動值 當最小波動值越大時，就說明營業情況越不穩定。 而分析整個公司的從成立到現在營業情況是否穩定，只需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程序幫助Tiger來計算這一個值。 第一天的最小波動值為第一天的營業額。  輸入輸出要求

Input

第一行為正整數 ，表示該公司從成立一直到現在的天數，接下來的n行每行有一個整數(有可能有負數) ，表示第i天公司的營業額。

Output

輸出文件僅有一個正整數，即Sigma(每天最小的波動值) 。結果小於2^31 。

Sample Input

Sample Output

HINT

結果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

此題數據有問題，詳見討論版http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1588

Source

平衡樹裸題，用來練習splay模板了。

據說這道題數據有點問題，讀入要寫if (scanf(“%d”,&x)==EOF) x=0;

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define pa pair
#define MAXN 50005
#define INF 1000000000
using namespace std;
int t[MAXN][2],fa[MAXN],num[MAXN],ans=0,rt=0,tot=0,x,t1,t2,n;
inline void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l,r;
	if (t[y][0]==x) l=0;else l=1;r=l^1;
	if (y==k) k=x;
	else{if (t[z][0]==y) t[z][0]=x;else t[z][1]=x;}
	fa[x]=z;fa[y]=x;fa[t[x][r]]=y;
	t[y][l]=t[x][r];t[x][r]=y;
}
inline void splay(int x,int &k)
{
	int y,z;
	while (x!=k)
	{
		y=fa[x];z=fa[y];
		if (y!=k)
		{
			if ((t[y][0]==x)^(t[z][0]==y)) rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}
inline void ins(int &k,int x,int last)
{
	if (!k){k=++tot;num[k]=x;fa[k]=last;splay(k,rt);return;}
	if (x=x){t2=num[k];getsuc(t[k][0],x);}
	else getsuc(t[k][1],x);
}
int main()
{
	scanf("%d",&n);
	F(i,1,n)
	{
		if (scanf("%d",&x)==EOF) x=0;
		t1=-INF;t2=INF;
		getpre(rt,x);
		getsuc(rt,x);
		if (i!=1) ans+=min(x-t1,t2-x);
		else ans+=x;
		ins(rt,x,0);
	}
	printf("%d\n",ans);
}