(HYSBZ)BZOJ 1588 营业额统计
营业额统计Time Limit: 5000MS Memory Limit: 165888KB 64bit IO Format: %lld & %llu

Description

Input

Output

Sample Input

Sample Output

Hint

/****Spaly的基本操作和应用****     求前驱与root的差和后驱与root的差,取最大,累加即可.     Rotate写的很精简,是学习别人的;     = =!他的源码有错误,不过却又不影响结果......     以后看别人的东西也要小心~~     *****************************/#include <map>#include <set>#include <list>#include <queue>#include <stack>#include <cmath>#include <ctime>#include <vector>#include <bitset>#include <cstdio>#include <string>#include <numeric>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <functional>using namespace std;typedef long long  ll;typedef unsigned long long ull;#define eps 1e-8#define inf 0x7fffffff#define debug puts("BUG")#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define read freopen("in.txt","r",stdin)#define write freopen("out.txt","w",stdout)#define Mem(a,x) memset(a,x,sizeof(a))#define maxn 100005int pre[maxn],key[maxn],ch[maxn][2],root,tot1;//分别表示父结点，键值，左右孩子(0为左孩子，1为右孩子),根结点，结点数量int n;int ans;void init(){    root=tot1=0;    ans=0;    Mem(key,0);}void NewNode(int &r,int father,int k){    r=++tot1;     //记录新节点的位置    pre[r]=father;//更新新节点的父亲    key[r]=k;    ch[r][0]=ch[r][1]=0;//左孩子和右孩子为空}void Rotate(int x,int k)//k为左旋和右旋的标志{    int y=pre[x];/**记录x的父亲**/    ch[y][!k]=ch[x][k];    pre[ch[x][k]]=y;    /**如果k=0, 表示从左到右旋转;如果k=1,表示从右到左旋转      *k=0, 表示x的位置由它的右孩子代替;      *k=1, 表示x的位置由它的左孩子代替.      *x的位置, 即为 !k    **/    if(pre[y])        ch[pre[y]][ch[pre[y]][1]==y]=x;    pre[x]=pre[y];    /** 更新x的父亲 和 x的新父亲的孩子节点(如果新的父亲存在)      * 如上    **/    ch[x][k]=y;    pre[y]=x;    /**更新y的父亲(即为x) 和 x的孩子节点      *如上    **/}void Splay(int r,int goal)//Splay调整,将r的值调整到目标位置goal{    while(pre[r]!=goal)    {        if(pre[pre[r]]==goal)//如果r的父亲就是根节点,goal的值为0,直接进行一次旋转即可        {            Rotate(r,ch[pre[r]][0]==r);        }        else//否则        {            int y= pre[r];            int k= ch[pre[y]][0]==y;//记录y与y的父亲的方向            if(ch[y][k]==r)//判断x与y和y的父亲是否在同一方向            {                //是 , 进行一字型旋转                Rotate(r,!k);//先左(右)旋                Rotate(r, k);//后右(左)旋            }            else            {                //否 , 进行之字形旋转                Rotate(y,k);//先对y进行左(右)旋                Rotate(r,k);//后对x进行右(左)旋            }        }    }    /**更新根节点**/    if(goal==0) root=r;}int Insert(int k)                 //将键值k插入到Splay中(Splay不为空){    int r=root;                   //从根节点开始    while(ch[r][key[r]<k])    {        //一直向下,找到叶子节点,根据二叉排序树的性质,查找时只需要比较key[r]与k的大小        if(key[r]==k)        {            //同一个值不需要再次插入,只需要进行Splay操作            Splay(r,0);            return 0;             //表示插入失败        }        r=ch[r][key[r]<k];        //未找到叶子节点,就需继续向下找    }    if(key[r]==k)    {        //同一个值不需要再次插入,只需要进行Splay操作        Splay(r,0);        return 0;             //表示插入失败    }    NewNode(ch[r][k>key[r]],r,k); //新建节点    Splay(ch[r][k>key[r]],0);     //Slay操作,插入的节点调整至根节点    return 1;                     //表示插入成功}int Get_pre(int x)//寻找前驱,即寻找左子树的最右点{    int temp=ch[x][0];    if(temp==0) return inf;    while(ch[temp][1])        temp=ch[temp][1];    return key[x]-key[temp];}int Get_next(int x)//寻找后继,即寻找右子树的最左点{    int temp=ch[x][1];    if(temp==0) return inf;    while(ch[temp][0])        temp=ch[temp][0];    return key[temp]-key[x];}/********************DEBUG***************************/void Puts(){    printf("root: %d\n",root);    for(int i=1;i<=tot1;i++)    {        printf("node: %d ,l is %d ,r is %d ,key : %d\n",i,ch[i][0],ch[i][1],key[i]);    }}/********************DEBUG END***********************/int main(){    while(~scanf("%d",&n))    {        init();        for(int i=1; i<=n; i++)        {            int x;            scanf("%d",&x);            if(i==1)            {                ans+=x;                NewNode(root,0,x);//建立Splay的第一个节点                continue;            }            if(Insert(x)==0)//插入,已经存在的值不需要插入            {continue;}            int a=Get_pre(root);//与前驱的差,可能不存在            int b=Get_next(root);//与后驱的差,也可能不存在            ans+=min(a,b);        }        printf("%d\n",ans);    }    return 0;}