P2234 [HNOI2002]营业额统计

题目描述

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。

第一天的最小波动值为第一天的营业额。

该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。

输入输出格式

输入格式：

输入由文件’turnover.in’读入。

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

输出格式：

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

//splay板子 

//题目中说：
// 该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}
//也就是说，我们在改天之前找一个和当天营业额最相近的数
//这样减出来的最小波动值最小
//也就是查询当天营业额的前驱、后继(包含与之相同的数)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=4e4+5;

int n;
struct NODE
{
    NODE *fa;
    NODE *son[2];
    int num;
    inline void update()
    {
        this->num=this->son[0]->num+this->son[1]->num;
    }
}node[N];

typedef NODE* Tree;
Tree Root,now_node,null;

inline int read()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar())
        f=c=='-'?-1:f;
    for(;isdigit(c);c=getchar())
        num=num*10+c-'0';
    return num*f;
}

inline void init()
{
    node->son[0]=node->son[1]=node->fa=node;
    Root=now_node=null=node;
}

inline Tree new_node(int num,Tree fa)
{
    ++now_node;
    now_node->num=num;
    now_node->fa=fa;
    now_node->son[0]=now_node->son[1]=null;
    return now_node;
}

inline bool getgx(Tree root)
{
    return root->fa->son[1]==root;
}

inline void connect(Tree root,Tree fa,bool flag)
{
    if(fa!=null)
        fa->son[flag]=root;
    root->fa=fa;
}

inline void rotate(Tree root)
{
    Tree fa=root->fa;
    bool a=getgx(root),b=!a;
    connect(root->son[b],fa,a);
    connect(root,fa->fa,getgx(fa));
    connect(fa,root,b);
}

inline void splay(Tree root,Tree goal)
{
    for(;root->fa!=goal;rotate(root))
    {
        if(root->fa->fa!=goal)
            rotate(getgx(root)==getgx(root->fa)?root->fa:root);
    }
    if(goal==null)
        Root=root;
}

inline void insert(int num)
{
    if(Root==null)
        Root=new_node(num,null);
    for(Tree root=Root;root!=null;root=root->son[num>root->num])
    {
        if(root->num==num)
        {
            splay(root,null);
            return;
        }
        else
            if(root->son[num>root->num]==null)
                root->son[num>root->num]=new_node(num,root);
    }
}

inline int query_pre(int num)
{
    int ans=-599518803;
    for(Tree root=Root;root!=null;root=root->son[num>root->num])
    {
        if(root->num<=num)
            ans=max(ans,root->num);
    }
    return ans;
}

inline int query_nxt(int num)
{
    int ans=599518803;
    for(Tree root=Root;root!=null;root=root->son[num>=root->num])
    {
        if(root->num>=num)
            ans=min(ans,root->num);
    }
    return ans;
}

int ans;
int main()
{
    init();
    n=read();
    ans=read();
    insert(ans);
    for(int i=2,a;i<=n;++i)
    {
        a=read();
        ans+=min(abs(query_pre(a)-a),abs(query_nxt(a)-a));
        insert(a);
    }
    printf("%d",ans);
    return 0;
}

Splay

// luogu-judger-enable-o2
//再旋转treap来一发
//什么时候学fhq treap。。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;

const int N=4e4+5;

int n;
struct NODE
{
    NODE *son[2];
    int key;
    int heap_key;
}node[N];

typedef NODE* Tree;
Tree Root,null,now_node;

inline int read()
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar())
        f=c=='-'?-1:f;
    for(;isdigit(c);c=getchar())
        num=num*10+c-'0';
    return num*f;
}

inline void init()
{
    srand(time(NULL));
    node->son[0]=node->son[1]=node;
    Root=null=now_node=node;
}

inline Tree new_node(int key)
{
    ++now_node;
    now_node->key=key;
    now_node->heap_key=rand();
    now_node->son[0]=now_node->son[1]=null;
    return now_node;
}

inline void rotate(Tree &root,bool flag)
{
    Tree tmp=root->son[!flag];
    root->son[!flag]=tmp->son[flag];
    tmp->son[flag]=root;
    root=tmp;
}

inline void insert(Tree &root,int key)
{
    if(root==null)
        root=new_node(key);
    else if(root->key==key)
        return;
    else
    {
        bool flag=key>root->key;
        insert(root->son[flag],key);
        if(root->son[flag]->heap_key>root->heap_key)
            rotate(root,!flag);
    }
}

inline int query_pre(int key)
{
    int ans=-599518803;
    for(Tree root=Root;root!=null;root=root->son[key>root->key])
    {
        if(root->key<=key)
            ans=max(ans,root->key);
    }
    return ans;
}

inline int query_nxt(int key)
{
    int ans=599518803;
    for(Tree root=Root;root!=null;root=root->son[key>=root->key])
    {
        if(root->key>=key)
            ans=min(ans,root->key);
    }
    return ans;
}

int ans;
int main()
{
    init();
    n=read();
    ans=read();
    insert(Root,ans);
    for(int i=2,a;i<=n;++i)
    {
        a=read();
        ans+=min(abs(query_pre(a)-a),abs(query_nxt(a)-a));
        insert(Root,a);
//        cout<<"ans:  "<<ans<<endl;
    }
    printf("%d",ans);
    return 0;
}

旋转treap