洛谷 P2234 [HNOI2002]营业额统计（算法竞赛进阶指南，平衡树）

算法竞赛进阶指南，238页，平衡树
本题要点：
1、该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。
每天的最小波动值， 实际就是改天的营业额 cur 和之前的所有营业额一起排序，计算出 cur 与相邻两个营业额
之间的差值的较小值，就是 该天的最小波动值
2、平衡树容易满足，每天的营业额 income 插入到这颗 平衡树中，计算出 income 的前驱 pre 和后继 next，
该天的最小波动值 = min( abs(income - pre), abs(income, next))

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 33000;
int tot, root, n, INF = 0x3f3f3f3f;struct Treap
{
    int l, r;int val, dat;
}a[MaxN];int New(int val)
{
    a[++tot].val = val;a[tot].dat = rand();return tot;
}void Build()
{
    New(-INF), New(INF);root = 1, a[1].r = 2;
}void zig(int &p)	//右旋转
{
    int q = a[p].l;a[p].l = a[q].r, a[q].r = p, p = q;
}void zag(int &p)	//左旋
{
    int q = a[p].r;a[p].r = a[q].l, a[q].l = p, p = q;
}void Insert(int &p, int val, bool &flag)
{
    if(0 == p){
    p = New(val);		return;}if(val == a[p].val){
    flag = true;	//存在return;}if(val < a[p].val){
    Insert(a[p].l, val, flag);if(a[p].dat < a[a[p].l].dat)	zig(p);	//不满足堆的条件，右旋}else{
    Insert(a[p].r, val, flag);if(a[p].dat < a[a[p].r].dat)    zag(p);}
}int GetPre(int val)
{
    int ans = 1;	//a[1].val = -INF;int p = root;while(p){
    if(val == a[p].val){
    if(a[p].l > 0){
    p = a[p].l;while(a[p].r > 0){
    p = a[p].r;		//左子树一直往右走}ans = p;}break;}if(a[p].val < val && a[p].val > a[ans].val)	ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}int GetNext(int val)
{
    int ans = 2;	//a[2].val = INFint p = root;while(p){
    if(val == a[p].val){
    if(a[p].r > 0){
    p = a[p].r;while(a[p].l > 0){
    p = a[p].l;	//右子树一直往左走}ans = p;}break;}if(a[p].val > val && a[p].val < a[ans].val){
    ans = p;}p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}int main()
{
    int income;Build();scanf("%d", &n);scanf("%d", &income);long long ans = income;int abs1, abs2;bool flag = false;Insert(root, income, flag);for(int i = 2; i <= n; ++i){
    flag = false;scanf("%d", &income);Insert(root, income, flag);if(flag)		//如果当前的营业额，之前已经存在，那么该天该天的最小波动值 = 0{
    continue;}abs1 = abs(income - GetPre(income));abs2 = abs(income - GetNext(income));ans += min(abs1, abs2);}printf("%lld\n", ans);return 0;
}/* 6 5 1 2 5 4 6 *//* 12 */