1565：营业额统计（平衡树）

 

 注意：以下代码最后一个点会 T，输入改成快读应该可以过

const int N=5e5+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    struct Node
    {
        int l,r;
        int fa,prl,val; //父节点，优先级，值
    }node[N];
    int root=0,tree=0; //根，节点个数


void zig(int &x) //右旋
{
    int y=node[x].l;
    node[x].l=node[y].r;
    node[y].r=x;
    x=y;
}

void zag(int &x) //左旋
{
    int y=node[x].r;
    node[x].r=node[y].l;
    node[y].l=x;
    x=y;
}

void insert(int &id,const int w)
{   
    if(!id){
        id=++tree;
        node[id].val=w;
        node[id].prl=rand();
        return ;
    }
    if(node[id].val>w){
        int L=node[id].l;
        insert(node[id].l,w);
        if(node[id].prl>node[L].prl) zig(id);
    } else{
        int R=node[id].r;
        insert(node[id].r,w);
        if(node[id].prl>node[R].prl) zag(id);
    }
}

int query_pre(const int w) //求比 w 小的最大数
{
    int id=root,ans=-inf;
    while(id){
        if(w>=node[id].val){ ans=node[id].val; id=node[id].r; }
        else id=node[id].l;
    }
    return ans;
}

int query_suf(const int w)
{
    int id=root,ans=inf;
    while(id){
        if(node[id].val>=w){ ans=node[id].val; id=node[id].l; }
        else id=node[id].r;
    }
    return ans;
}

int main()
{
    while(~sd(n)){
        for(i=1;i<=n;i++) sd(a[i]);
        int ans=a[1];
        insert(root,a[1]);
        int x,y;
        for(i=2;i<=n;i++){
            x=query_pre(a[i]);
            y=query_suf(a[i]);
            ans+=min(a[i]-x,y-a[i]);
            //dbg(root);
            insert(root,a[i]);
        }
        pd(ans);
    }
    //PAUSE;
    return 0;
}