学步园

（以上是完整的题，注意:每行有一个整数ai，而非正整数。还有，本题在lydsy上的评测数据有问题（具体参见lydsy上本题的评论））。

评测链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1588

解法：SBT。

对于第i天的营业额ai，它的最小波动值m就等于从1号到i-1天中，与它大小最接近的营业额p与ai差值的绝对值。那么由此可以想到，在将ai插入sbt树时，所经过的节点中，必定有一个就是就是我们要找的p号点，也就得到第i天的最小波动值m=min{m,abs(p[t]-a[i])}，p[t]是ai插入sbt树时途经的点t的营业额值。

由此基本思路就出来了，维护一棵sbt树，每次插入时维护出最小波动值m，然后将每次的m累加起来即可。

以下是我在自己电脑上用正确数据评测用的程序代码：

#include<cstdio>
#include<cmath>
#include<cctype>
#include<algorithm>
#define maxn (32767+1000)
#define inf 100000000
using namespace std;

int n,root=0,ans=0,m,num,w;
int l[maxn],r[maxn],s[maxn],p[maxn];

void init()
{
  freopen("turnover.in","r",stdin);
  freopen("turnover.out","w",stdout);
}

inline void right_rotate(int &t)
{
  int k=l[t];
  l[t]=r[k];
  r[k]=t;
  s[k]=s[t];
  s[t]=s[l[t]]+s[r[t]]+1;
  t=k;  
}

inline void left_rotate(int &t)
{
  int k=r[t];
  r[t]=l[k];
  l[k]=t;
  s[k]=s[t];
  s[t]=s[l[t]]+s[r[t]]+1;
  t=k;
}

void maintain(int &t,bool flag)
{
  if(flag)
    if(s[l[l[t]]]>s[r[t]])
      right_rotate(t);
    else
      if(s[r[l[t]]]>s[r[t]])
        left_rotate(l[t]),right_rotate(t);
      else
        return;
  else
    if(s[r[r[t]]]>s[l[t]])
      left_rotate(t);
    else
      if(s[l[r[t]]]>s[l[t]])
        right_rotate(r[t]),left_rotate(t);
      else
        return;
  maintain(l[t],1);
  maintain(r[t],0);
  maintain(t,1);
  maintain(t,0);                      
}

void insert(int &t)
{
  if(t==0)
    {
      t=num; ans+=m;
      s[t]=1,l[t]=r[t]=0,p[t]=w;
      return;
    }
  s[t]++; m=min(m,abs(w-p[t]));
  if(w<p[t])insert(l[t]);
  else insert(r[t]);
  maintain(t,w<p[t]);  
}

void work()
{
  scanf("%d",&n);
  scanf("%d",&ans);
  s[0]=l[0]=r[0]=0;      
  root=s[1]=1,p[1]=ans,l[1]=r[1]=0;

  for(int i=2;i<=n;i++)
    {
      m=inf,num=i,w=0;
      scanf("%d",&w);
      insert(root);
    }
  printf("%d\n",ans);   
}

int main()
{
  init();
  work();
  return 0;
}

以下是我提交到lydsy上评测用的程序代码：

#include<cstdio>
#include<cmath>
#include<cctype>
#include<algorithm>
#define maxn (32767+1000)
#define inf 100000000
using namespace std;

int n,root=0,ans=0,m,num,w;
int l[maxn],r[maxn],s[maxn],p[maxn];

void init()
{
  freopen("turnover.in","r",stdin);
  freopen("turnover.out","w",stdout);
}

inline void right_rotate(int &t)
{
  int k=l[t];
  l[t]=r[k];
  r[k]=t;
  s[k]=s[t];
  s[t]=s[l[t]]+s[r[t]]+1;
  t=k;  
}

inline void left_rotate(int &t)
{
  int k=r[t];
  r[t]=l[k];
  l[k]=t;
  s[k]=s[t];
  s[t]=s[l[t]]+s[r[t]]+1;
  t=k;
}

void maintain(int &t,bool flag)
{
  if(flag)
    if(s[l[l[t]]]>s[r[t]])
      right_rotate(t);
    else
      if(s[r[l[t]]]>s[r[t]])
        left_rotate(l[t]),right_rotate(t);
      else
        return;
  else
    if(s[r[r[t]]]>s[l[t]])
      left_rotate(t);
    else
      if(s[l[r[t]]]>s[l[t]])
        right_rotate(r[t]),left_rotate(t);
      else
        return;
  maintain(l[t],1);
  maintain(r[t],0);
  maintain(t,1);
  maintain(t,0);                      
}

void insert(int &t)
{
  if(t==0)
    {
      t=num; ans+=m;
      s[t]=1,l[t]=r[t]=0,p[t]=w;
      return;
    }
  s[t]++; m=min(m,abs(w-p[t]));
  if(w<p[t])insert(l[t]);
  else insert(r[t]);
  maintain(t,w<p[t]);  
}

void work()
{
  scanf("%d",&n);
  scanf("%d",&ans);
  s[0]=l[0]=r[0]=0;      
  root=s[1]=1,p[1]=ans,l[1]=r[1]=0;

  for(int i=2;i<=n;i++)
    {
      m=inf,num=i,w=0;
      scanf("%d",&w);
      insert(root);
    }
  printf("%d\n",ans);   
}

int main()
{
  init();
  work();
  return 0;
}