BZOJ1588_营业额统计_KEY

题目传送门

分析题意可得，希望求与每个数最相近的数。

二叉搜索树的简单题，因为可能被卡成O(N),考虑平衡树。

因为Treap较简单，此处用Treap编写代码。

code：

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

char tc()

{

    static char fl[],*A=fl,*B=fl;

    return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;

}

int read()

{

    char c;while(c=tc(),(c<''||c>'')&&c!='-');int x=,y=;c=='-'?y=-:x=c-'';

    while(c=tc(),c>=''&&c<='')x=x*+c-'';

    return x*y;

}

int x,ans;

int N,v[],tp[][],r[],cnt,rt;

int rotate(int &now,int x)

{

    int k=tp[now][x];

    tp[now][x]=tp[k][x^];

    tp[k][x^]=now;

    now=k;

}

int pre(int o,int x)

{

    int res=2e9;

        while(o){

            res=min(res,abs(v[o]-x));

            o=tp[o][v[o]<x];

        }

    return res;

}

void insert(int &now,int x)

{

    if(!now){

        now=++cnt;

        v[now]=x;r[now]=rand();

        return ;

    }

    if(x==v[now])return ;

     int to=x>v[now];

    insert(tp[now][to],x);

    if(r[now]<r[tp[now][to]])rotate(now,to);

}

main()

{

//    freopen("x.txt","r",stdin);

    N=read();

        for(int i=;i<=N;i++){

            x=read();

            if(i==)ans+=x;

            else ans+=pre(rt,x);

            insert(rt,x);

        }

    printf("%d",ans);

    return ;

}