Description

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

Input

第一行為正整數(shù) ，表示該公司從成立一直到現(xiàn)在的天數(shù)，接下來的n行每行有一個整數(shù)(有可能有負(fù)數(shù)) ，表示第i
天公司的營業(yè)額。
天數(shù)n<=32767,
每天的營業(yè)額ai <= 1,000,000。
最后結(jié)果T<=2^31

Output

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

一道裸的splay題。
題目大意時每次插入一個數(shù)，同時尋找與當(dāng)前數(shù)差值最小的數(shù)。
隨機數(shù)據(jù)可以用二叉樹直接過，但是如果所有的數(shù)是單調(diào)遞減的，那么復(fù)雜度就退化到了O(n^2)。
考慮splay，每次插入一個數(shù)splay后，再BST內(nèi)尋找前驅(qū)和后繼。
時間復(fù)雜度保證為O(nlogn)。

P.S:代碼中rotate和splay的壓行寫法不是很推薦，因為比賽時這樣寫很容易寫崩。

#include
#include
#include
#define maxn 100050
#define INF 1000000000
using namespace std;
typedef long long ll;
struct node
{
????int f,s[2],w; //father,leftson,rightson
}a[maxn*2];
int dfn=0,root,y,z,bo,n,x,p,q,hz;
ll ans=0ll;
inline void rotate(int x,int k) //k=0左旋,k=1右旋
{
????y=a[x].f,z=a[y].f,a[y].s[!k]=a[x].s[k];
????if (a[x].s[k]!=-1) a[a[x].s[k]].f=y;
????if (z!=-1) a[z].s[a[z].s[1]==y]=x;
????a[x].f=z,a[y].f=x,a[x].s[k]=y;
}
inline void splay(int x)
{
????while (a[x].f!=-1)
????{
????????int y=a[x].f,z=a[y].f;
????????if (z==-1) rotate(x,a[y].s[0]==x);
????????else
????????{
????????????if (a[z].s[0]==y) {if (a[y].s[0]==x) rotate(y,1),rotate(x,1);else rotate(x,0),rotate(x,1);}
????????????else {if (a[y].s[1]==x) rotate(y,0),rotate(x,0);else rotate(x,1),rotate(x,0);}
????????}
????}
????root=x;
}
inline int pre(int x) ??//尋找前驅(qū)
{
????int tmp=a[x].s[0];
????if (tmp==-1) return tmp;
????while (a[tmp].s[1]!=-1) tmp=a[tmp].s[1];
????return tmp;
}
inline int suc(int x) ?//尋找后繼
{
????int tmp=a[x].s[1];
????if (tmp==-1) return tmp;
????while (a[tmp].s[0]!=-1) tmp=a[tmp].s[0];
????return tmp;
}
inline void insert(int now,int x)
{
????if (a[x].w==now) {bo=0,splay(x);return;} ??//已有相同元素的節(jié)點
????if (now ????{
????????if (a[x].s[0]==-1) a[x].s[0]=dfn,a[dfn].f=x,a[dfn].s[0]=a[dfn].s[1]=-1,a[dfn].w=now;
????????else insert(now,a[x].s[0]);
????}
????else
????{
????????if (a[x].s[1]==-1) a[x].s[1]=dfn,a[dfn].f=x,a[dfn].s[0]=a[dfn].s[1]=-1,a[dfn].w=now;
????????else insert(now,a[x].s[1]);
????}
}
int main()
{
????scanf("%d",&n);
????scanf("%d",&x);
????ans=x,dfn++,a[dfn].f=a[dfn].s[0]=a[dfn].s[1]=-1,a[dfn].w=x,root=dfn; ?//建立根節(jié)點
????for (int i=1;i ????{
????????scanf("%d",&x);
????????bo=1,dfn++,insert(x,root);
????????if (!bo) continue; ?//已有過相同元素的節(jié)點，那么該點對答案肯定沒有貢獻(xiàn)
????????splay(dfn),p=pre(dfn),q=suc(dfn),hz=INF;
????????if (p!=-1) hz=min(hz,abs(x-a[p].w));
????????if (q!=-1) hz=min(hz,abs(x-a[q].w));
????????ans+=hz; ??//比較x與其前驅(qū)與后繼的距離后累加答案
????}
????printf("%lld",ans);
}?