bzoj1588 [HNOI2002]營業額統計

1588: [HNOI2002]營業額統計

Time Limit:?5 Sec??Memory Limit:?162 MB
Submit:?17931??Solved:?7391
[Submit][Status][Discuss]

Description

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

Input

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

天公司的營業額。

天數n<=32767,

每天的營業額ai <= 1,000,000。

最后結果T<=2^31

?

Output

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

Sample Input

6
5
1
2
5
4
6

Sample Output

12

HINT

?

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

該題數據bug已修復.----2016.5.15

分析：splay裸題，每次找前驅和后繼，找前驅的方法是在左子樹中找最大的數（一直往右跳），后繼就是在右子樹中找最小的數（往左跳）.需要注意的是每次插入完一個數都要將它翻到上面去.并且要更新根節點！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int maxn = 40010;struct node
{int fa,left,right,v;
}e[maxn];int n,ans,Time,t,root = 1;
bool flag = true;void turnr(int x)
{int y = e[x].fa;int z = e[y].fa;e[y].left = e[x].right;if (e[x].right != -1)e[e[x].right].fa = y;e[x].fa = z;if (z != -1){if (e[z].left == y)e[z].left = x;elsee[z].right = x;}e[x].right = y;e[y].fa = x;
}void turnl(int x)
{int y = e[x].fa;int z = e[y].fa;e[y].right = e[x].left;if (e[x].left != -1)e[e[x].left].fa = y;e[x].fa = z;if (z != -1){if (e[z].left == y)e[z].left = x;elsee[z].right = x;}e[x].left = y;e[y].fa = x;
}void splay(int x)
{while (e[x].fa != -1){int y = e[x].fa;int z = e[y].fa;if (z == -1){if (x == e[y].left)turnr(x);elseturnl(x);}else{if (e[z].left == y && e[y].left == x){turnr(y);turnr(x);}else{if (e[z].right == y && e[y].right == x){turnl(y);turnl(x);}else{if (e[z].left == y && e[y].right == x){turnl(x);turnr(x);}else{turnr(x);turnl(x);}}}}}root = x;
}void insert(int x,int y)
{if (x == e[y].v){flag = false;splay(y);return;}if (x < e[y].v){if (e[y].left == -1){e[y].left = ++Time;e[Time].left = e[Time].right = -1;e[Time].fa = y;e[Time].v = x;}elseinsert(x,e[y].left);}else{if (e[y].right == -1){e[y].right = ++Time;e[Time].left = e[Time].right = -1;e[Time].fa = y;e[Time].v = x;}elseinsert(x,e[y].right);}
}int findl(int x)
{int y = e[x].left;if (y == -1)return y;while (e[y].right != -1)y = e[y].right;return y;
}int findr(int x)
{int y = e[x].right;if (y == -1)return y;while (e[y].left != -1)y = e[y].left;return y;
}void solve(int x)
{flag = true;insert(x,root);if (!flag)return;splay(Time);int p = findl(Time),q = findr(Time);int temp = 0x7fffffff;if (p != -1)temp = min(temp,abs(x - e[p].v));if (q != -1)temp = min(temp,abs(x - e[q].v));if (temp != 0x7fffffff)ans += temp;
}int main()
{scanf("%d",&n);scanf("%d",&t);ans += t;e[++Time].fa = -1;e[Time].left = -1;e[Time].right = -1;e[Time].v = t;for (int i = 2; i <= n; i++){scanf("%d",&t);solve(t);}printf("%d\n",ans);return 0;
}

?