[bzoj] 1588 营业额统计 || Splay板子题

原题

给出一个n个数的数列ai ,对于第i个元素ai定义\(fi=min(|ai-aj|) (1<=j<i)\)，f1=a1,求\(/sumfi\)

Splay板子题。

Splay讲解：http://www.cnblogs.com/mrsheep/p/8110483.html

//太懒了……

#include<cstdio>

#include<algorithm>

#include<cmath>

#define which(x) (ls[f[(x)]]==(x))

#define N 33000

using namespace std;

int n,v,root,ls[N],rs[N],val[N],f[N],idx,ans;

void Rotate(int u)

{

    int v=f[u],w=f[v],b=which(u)?rs[u]:ls[u],dir=which(v);

    which(u)?(rs[u]=v,ls[v]=b):(ls[u]=v,rs[v]=b);

    f[v]=u;f[b]=v;f[u]=w;

    if (w) dir?ls[w]=u:rs[w]=u;

}

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

void splay(int x,int y)

{

    while (f[x]!=y)

    {

    if (f[f[x]]!=y)

    {

        if (which(x)==which(f[x])) Rotate(f[x]);

        else Rotate(x);

    }

    Rotate(x);

    }

    if (!y) root=x;

}

void insert(int x)

{

    int u=root,v=0;

    while (u)

    {

    v=u;

    if (x<val[u]) u=ls[u];

    else u=rs[u];

    }

    f[++idx]=v;

    val[idx]=x;

    if (v) x<val[v]?ls[v]=idx:rs[v]=idx;

    splay(idx,0);

}

int getmx(int x)

{

    if (!x) return 97797977;

    while (rs[x]) x=rs[x];

    return val[x];

}

int getmn(int x)

{

    if (!x) return 97797977;

    while (ls[x]) x=ls[x];

    return val[x];

}

int query()

{

    int lmx=getmx(ls[root]),rmn=getmn(rs[root]);

    return min(abs(val[root]-lmx),abs(val[root]-rmn));

}

int main()

{

    n=read();

    v=read();

    insert(v);

    ans+=v;

    for (int i=2;i<=n;i++)

    {

    v=read();

    insert(v);

    ans+=query();

    }

    printf("%d",ans);

    return 0;

}

巴特西

[bzoj] 1588 营业额统计 || Splay板子题

原题

最新文章

热门文章