HYSBZ 1588 营业额统计

Description

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

Input

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

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

此题数据有问题，详见讨论版http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1588

简单的splay问题，找到前驱和后继即可

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 3e5 + 10;
int n, m, root, ans, x;

struct Splays
{
  const static int maxn = 3e5 + 10;     //节点个数
  const static int INF = 0x7FFFFFFF;      //int最大值
  int ch[maxn][2], F[maxn], sz;       //左右儿子，父亲节点和节点总个数
  int A[maxn];
  int Node(int f, int u) { ch[sz][0] = ch[sz][1] = 0; F[sz] = f; A[sz] = u; return sz++; }//申请一个新节点
  void clear(){ sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; }//清空操作
  void rotate(int x, int k)
  {
    int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
    if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
    F[x] = F[y];    F[y] = x; ch[x][k] = y;
  }
  void Splay(int x, int r)
  {
    for (int fa = F[r]; F[x] != fa;)
    {
      if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
      int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
      y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
    }
  }
  int insert(int&x, int y)
  {
    if (!x) { x = Node(0, y); return y; }
    for (int i = x; i; i = ch[i][A[i] < y])
    {
      if (A[i] == y) { Splay(i, x); x = i; return 0; }
      if (!ch[i][A[i] < y])
      {
        i = ch[i][A[i] < y] = Node(i, y);
        Splay(i, x); x = i; break;
      }
    }
    int ans = INF;
    for (int i = ch[x][0]; i; i = ch[i][1])
    {
      ans = min(ans, y - A[i]);
    }
    for (int i = ch[x][1]; i; i = ch[i][0])
    {
      ans = min(ans, A[i] - y);
    }
    return ans;
  }
}solve;

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    solve.clear();  ans = root = 0;
    while (n--)
    {
      if (scanf("%d", &x) != 1) x = 0;//数据问题
      ans+=solve.insert(root, x);
    }
    printf("%d\n", ans);
  }
  return 0;
}