「Luogu P2234」[HNOI2002]营业额统计

给定一个数列$a$，对于$a_i$，寻找一个$a_j$使得$i>j$且$\vert a_i-a_j\vert$最小。

题解

一道近乎Splay裸题的题。
很显然可以将最小的$\vert a_i-a_j\vert$拆成$a_i$与其前驱的差和与其后继的差的最小值。
所以说就可以用Splay维护啦qwq。
论手贱，你是比不过我的，今天又把while打成if啦

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=4e4+51,inf=0x3f3f3f3f;
ll cnt,num,res,prv,nxt;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
namespace Splay{
    struct Node{
        ll fa,val,size,temp;
        ll ch[2];
        inline void reset(ll val=0,ll fa=0)
        {
            this->fa=fa,this->val=val,this->temp=this->size=1;
            this->ch[0]=this->ch[1]=0;
        }
    };
    struct Splay{
        ll tot,root;
        Node nd[MAXN];
        inline bool id(ll x)
        {
            return nd[nd[x].fa].ch[1]==x;
        }
        inline void update(ll x)
        {
            nd[x].size=nd[nd[x].ch[0]].size+nd[nd[x].ch[1]].size+nd[x].temp;
        }
        inline void connect(ll x,ll fa,ll dir)
        {
            nd[x].fa=fa,nd[fa].ch[dir]=x;
        }
        inline void rotate(ll x)
        {
            ll fa=nd[x].fa,gfa=nd[fa].fa,dir=id(x);
            connect(x,gfa,id(fa));
            connect(nd[x].ch[dir^1],fa,dir);
            connect(fa,x,dir^1);
            update(fa),update(x);
        }
        inline void splay(ll cur,ll target)
        {
            while(nd[cur].fa!=target)
            {
                ll fa=nd[cur].fa,gfa=nd[fa].fa;
                if(gfa!=target)
                {
                    rotate(id(cur)^id(fa)?cur:fa);
                }
                rotate(cur);
            }
            if(!target)
            {
                root=cur;
            }
        }
        inline void insert(ll val)
        {
            ll cur=root,fa=0;
            while(cur&&nd[cur].val!=val)
            {
                fa=cur,cur=nd[cur].ch[val>nd[cur].val];
            }
            if(cur)
            {
            	nd[cur].temp++;
            }
            else
            {
            	cur=++tot;
                if(fa)
                {
                   nd[fa].ch[val>nd[fa].val]=cur;
                }
                nd[cur].reset(val,fa);
            }
            splay(cur,0);
        }
        inline void find(ll val)
        {
            ll cur=root;
            if(!cur)
            {
            	return;
            }
            while(nd[cur].ch[val>nd[cur].val]&&val!=nd[cur].val)
            {
                cur=nd[cur].ch[val>nd[cur].val];
            }
            splay(cur,0);
        } 
        inline ll prev(ll val)
        {
            find(val);
            ll cur=root;
            if(nd[cur].val<=val)
            {
                return nd[cur].val;
            }
            cur=nd[cur].ch[0];
            while(nd[cur].ch[1])
            {
                cur=nd[cur].ch[1];
            }
            return nd[cur].val;
        }
        inline ll next(ll val)
        {
            find(val);
            ll cur=root;
            if(nd[cur].val>=val)
            {
                return nd[cur].val;
            }
            cur=nd[cur].ch[1];
            while(nd[cur].ch[0])
            {
                cur=nd[cur].ch[0];
            }
            return nd[cur].val;
        }
    };
}
Splay::Splay splay;
int main()
{
    cnt=read();
    splay.insert(inf),splay.insert(-inf);
    splay.insert(res=read()); 
    for(register int i=1;i<cnt;i++)
    {
        num=read();
        prv=splay.prev(num),nxt=splay.next(num);
        res+=min(num-prv,nxt-num);
        splay.insert(num);
    }
    printf("%d",res);
}