1588. [HNOI2002]营业额统计【平衡树-splay 或线段树】

Description

营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：该天的最小波动值当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。  输入输出要求

Input

第一行为正整数，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i

天公司的营业额。

天数n<=32767,

每天的营业额ai <= 1,000,000。

最后结果T<=2^31

Output

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

Sample Input

6
5
1
2
5
4
6

Sample Output

HINT

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

第一个为线段树做法第二个为平衡树做法

线段树：
设每天的营业额在线段树数组中的下标为他本身的值
然后每次输入一个数时我们先在这个数的左边的区间查找最大值
再在右边的区间查找最小值
（这意味着我们要找比这个数小的最大值和比这个数大的最小值）
然后比较两者取差的绝对值最小的加到Ans里即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXN (32767+5)
#define MAX (2000000)
using namespace std;

struct node
{
    int max,min;
}Segt[MAX*4+5];

int n,a[MAXN],INF,ans;

void Update(int node,int l,int r,int x,int k)
{
    if (l==r)
        Segt[node].max=Segt[node].min=k;
    else
    {
        int mid=(l+r)/2;
        if (x<=mid)    Update(node*2,l,mid,x,k);
        if (x>mid)    Update(node*2+1,mid+1,r,x,k);
        Segt[node].max=max(Segt[node*2].max,
                           Segt[node*2+1].max);
        Segt[node].min=min(Segt[node*2].min,
                           Segt[node*2+1].min);
    }
}

int QueryMax(int node,int l,int r,int l1,int r1)
{
    if (l>r1||r<l1)
        return -INF;
    if (l1<=l && r<=r1)
        return Segt[node].max;
    int mid=(l+r)/2;
    return max(QueryMax(node*2,l,mid,l1,r1),
               QueryMax(node*2+1,mid+1,r,l1,r1));
}

int QueryMin(int node,int l,int r,int l1,int r1)
{
    if (l>r1||r<l1)
        return INF;
    if (l1<=l && r<=r1)
        return Segt[node].min;
    int mid=(l+r)/2;
    return min(QueryMin(node*2,l,mid,l1,r1),
               QueryMin(node*2+1,mid+1,r,l1,r1));
}

int main()
{
    memset(&INF,0x7f,sizeof(INF));
    for (register int i=0;i<=8000000;++i)
        Segt[i].min=INF,Segt[i].max=-INF;
    
    struct node Segt;
    Segt.min=INF;
    Segt.max=-INF;
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if (i==1) 
        {
            Update(1,0,MAX,a[i]+MAX/2,a[i]+MAX/2);
            ans+=a[i];
            continue;
        }
        int x=QueryMax(1,0,MAX,0,a[i]+MAX/2)-MAX/2;
        int y=QueryMin(1,0,MAX,a[i]+MAX/2,MAX)-MAX/2;
        Update(1,0,MAX,a[i]+MAX/2,a[i]+MAX/2);
        ans+=min(abs(a[i]-x),abs(a[i]-y));
    }
    printf("%d",ans);
}

平衡树：

近乎Splay裸题了……
一天天插入数字，然后查询前驱和后继累加最小值就好了
注意若当前天营业额在之前出现过时（即为Cnt>1）就不用累加了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #define MAXN (50000)
  6 using namespace std;
  7 
  8 int Cnt[MAXN];
  9 int Size[MAXN];
 10 int Key[MAXN];
 11 int Father[MAXN];
 12 int Son[MAXN][2];
 13 int SIZE,ROOT;
 14 int INF;
 15 
 16 void Clear(int x)
 17 {
 18     Cnt[x]=Size[x]=Key[x]=Father[x]=Son[x][1]=Son[x][2]=0;
 19 }
 20 
 21 void Update(int x)
 22 {
 23     if (x)
 24     {
 25         Size[x]+=Cnt[x];
 26         if (Son[x][0])    Size[x]+=Cnt[Son[x][0]];
 27         if (Son[x][1])    Size[x]+=Cnt[Son[x][1]];
 28     }
 29 }
 30 
 31 int Get(int x)
 32 {
 33     return Son[Father[x]][1]==x;
 34 }
 35 
 36 void Rotate(int x)
 37 {
 38     int fa=Father[x];
 39     int fafa=Father[fa];
 40     int wh=Get(x);
 41     Father[fa]=x;
 42     Son[fa][wh]=Son[x][wh^1];
 43     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
 44     Son[x][wh^1]=fa;
 45     Father[x]=fafa;
 46     if     (fafa)  Son[fafa][Son[fafa][1]==fa]=x;
 47     Update(fa);
 48     Update(x);
 49 }
 50 
 51 void Splay(int x)
 52 {
 53     for (int fa;fa=Father[x];Rotate(x))
 54         if (Father[fa])
 55             Rotate(Get(x)==Get(fa)?fa:x);
 56     ROOT=x;
 57 }
 58 
 59 void Insert(int x)
 60 {
 61     if (ROOT==0)
 62     {
 63         ROOT=++SIZE;
 64         Key[SIZE]=x;
 65         Cnt[SIZE]=Size[SIZE]=1;
 66         return;
 67     }
 68     int now=ROOT,fa=0;
 69     while (1)
 70     {
 71         if(Key[now]==x)
 72         {
 73             ++Cnt[now];
 74             Update(now);
 75             Splay(now);
 76             return;
 77         }
 78         fa=now;now=Son[now][x>Key[now]];
 79         if (now==0)
 80         {
 81             ++SIZE;
 82             Key[SIZE]=x;
 83             Cnt[SIZE]=Size[SIZE]=1;
 84             Father[SIZE]=fa;
 85             Son[fa][x>Key[fa]]=SIZE;
 86             Update(fa);
 87             Splay(SIZE);
 88             return;
 89         }
 90     }
 91 }
 92 
 93 int Pre()
 94 {
 95     int now=Son[ROOT][0];
 96     if (now==0) return INF;
 97     while (Son[now][1])
 98         now=Son[now][1];
 99     return Key[now];
100 }
101 
102 int Next()
103 {
104     int now=Son[ROOT][1];
105     if (now==0) return INF;
106     while (Son[now][0])
107         now=Son[now][0];
108     return Key[now];
109 }
110 
111 int main()
112 {
113     int n,x,Ans=0;
114     memset(&INF,0x7f,sizeof(INF));
115     scanf("%d",&n);
116     for (int i=1;i<=n;++i)
117     {
118         scanf("%d",&x);
119         Insert(x);
120         if (i==1)
121             Ans+=x;
122         else
123             if (Cnt[ROOT]<=1)
124                 Ans+=min(abs(x-Pre()),abs(x-Next()));
125     }
126     printf("%d",Ans);
127 }