HNOI2002 营业额统计 [Treap]

这道题还是Treap查找前驱/后继。

与HNOI2004 宠物收养场这题不同的地方在于这题的前驱和后继是可以等于其原数的。。。

开始我没注意到，结果疯狂WA。。。

#include <bits/stdc++.h>

const int inf=0x3f3f3f3f;

int N,Ans;

struct Treap
{
    Treap *ch[];
    int size,cnt,r,v;
    Treap(int x)
    {
        size=cnt=;
        r=rand();
        v=x;
        ch[]=ch[]=NULL;
    }
    int cmp(int x)
    {
        if(x==v) return -1;
        return x>v;
    }
    void maintain()
    {
        size=cnt+((ch[]==NULL)?:ch[]->size)+((ch[]==NULL)?:ch[]->size);
    }
}*root;

void rotate(Treap* &o,int d)
{
    Treap *k=o->ch[d^];
    o->ch[d^]=k->ch[d];
    k->ch[d]=o;
    o->maintain(),k->maintain();
    o=k;
}

void insert(Treap* &o,int x)
{
    if(o==NULL) o=new Treap(x);
    else
    {
        if(o->v==x) ++(o->cnt);
        else
        {
            int d=o->cmp(x);
            insert(o->ch[d],x);
            if(o->ch[d]->r>o->r) rotate(o,d^);
        }
    }
    o->maintain();
}

int upper(Treap *o,int x)
{
    if(o==NULL) return -inf;
    else if(o->cmp(x)!=) return std::max(o->v,upper(o->ch[],x));
    else return upper(o->ch[],x);
}

int lower(Treap *o,int x)
{
    if(o==NULL) return inf;
    else if(o->cmp(x)!=) return std::min(o->v,lower(o->ch[],x));
    else return lower(o->ch[],x);
}

inline int read()
{
    register int x=,v=;
    register char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') v=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<)+(x<<)+ch-'0';
        ch=getchar();
    }
    return x*v;
}

int main()
{
    int t;
    N=read();
    for(register int i=;i<=N;++i)
    {
        t=read();
        if(root==NULL) Ans+=t;
        else Ans+=std::min(lower(root,t)-t,t-upper(root,t));
        insert(root,t);
    }
    printf("%d\n",Ans);
    return ;
}