HNOI2002(伸展树)

营业额统计

Time Limit:5000MS Memory Limit:165888KB 64bit IO Format:%lld & %llu

Description

营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：该天的最小波动值当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。  输入输出要求

Input

第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i天公司的营业额。

Output

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

Sample Input

Sample Output

12

初学伸展树，先借鉴了他人的模板

  1 //2016.8.12
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 const int N = 100005;
  9 const int inf = 0x3f3f3f3f;
 10 int root , tot, pre[N], key[N], child[N][2];//分别表示根节点、节点总数、父节点、键值、孩子(左0右1)
 11 
 12 void NewNode(int &r, int father, int k)//创建新节点
 13 {
 14     r = ++tot;
 15     pre[r] = father;
 16     key[r] = k;
 17     child[r][0] = child[r][1] = 0;//叶子节点，孩子为空
 18 }
 19 
 20 void Rotato(int x, int kind)//旋转，kind为1则右旋，为0则左旋
 21 {
 22     int y = pre[x];
 23     child[y][!kind] = child[x][kind];
 24     pre[child[x][kind]] = y;
 25     if(pre[y])
 26       child[pre[y]][child[pre[y]][1]==y] = x;
 27     pre[x] = pre[y];
 28     child[x][kind] = y;
 29     pre[y] = x;
 30 }
 31 
 32 void Splay(int r, int goal)//Splay调整，将r节点调到goal节点下面
 33 {
 34     while(pre[r] != goal)
 35     {
 36         if(pre[pre[r]]==goal)
 37           Rotato(r, child[pre[r]][0]==r);
 38         else
 39         {
 40             int y = pre[r];
 41             int kind = child[pre[y]][0]==y;
 42             if(child[y][kind] == r)
 43             {
 44                 Rotato(r, !kind);
 45                 Rotato(r, kind);
 46             }else
 47             {
 48                 Rotato(y, kind);
 49                 Rotato(r, kind);
 50             }
 51         }
 52     }
 53     if(goal == 0)root = r;//更新根节点
 54 }
 55 
 56 int ins(int k)//插入
 57 {
 58     int r = root;
 59     while(child[r][key[r]<k])
 60     {
 61         if(key[r] == k)//不重复插入
 62         {
 63             Splay(r, 0);
 64             return 0;
 65         }
 66         r = child[r][key[r]<k];
 67     }
 68     NewNode(child[r][key[r]<k], r, k);
 69     Splay(child[r][key[r]<k], 0);
 70     return 1;
 71 }
 72 
 73 int get_pre(int x)//找前驱
 74 {
 75     int tmp = child[x][0];
 76     if(tmp==0)return inf;
 77     while(child[tmp][1])
 78     {
 79         tmp = child[tmp][1];
 80     }
 81     return key[x]-key[tmp];
 82 }
 83 
 84 int get_next(int x)//找后继
 85 {
 86     int tmp = child[x][1];
 87     if(tmp==0)return inf;
 88     while(child[tmp][0])
 89     {
 90         tmp = child[tmp][0];
 91     }
 92     return key[tmp]- key[x];
 93 }
 94 
 95 int main()
 96 {
 97     int n, ans, num;
 98     while(cin>>n)
 99     {
100         root = tot = ans = 0;
101         for(int i = 0; i < n; i++)
102         {
103             scanf("%d", &num);
104             if(i==0)
105             {
106                 ans+=num;
107                 NewNode(root, 0, num);
108                 continue;
109             }
110             if(ins(num)==0)continue;
111             int l = get_pre(root);
112             int r = get_next(root);
113             ans+=min(l, r);
114         }
115         printf("%d
", ans);
116     }
117 
118     return 0;
119 }