树状数组 HNOI2002 营业额统计

1533. [HNOI2002]营业额统计

★★★ 输入文件：turnover.in 输出文件：turnover.out 简单对比
时间限制：5 s 内存限制：162 MB

【题目描述】

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。

第一天的最小波动值为第一天的营业额。

【输入格式】

第一行为正整数n(n<=32767)，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数ai(ai<=1000000)，表示第i天公司的营业额。

【输出格式】

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

【样例输入】

【样例输出】

【提示】

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

【来源】

HNOI 2002

听说这个是SPLAY,可是我还没码熟，只好瞎写一个树状数组骗一骗

好像莫名其妙被卡了read()，算法没问题

贴代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int n;
 8 int in[40010];
 9 int maxn,minn;
10 int ans;
11 int z0[1100010],z1[1100010];
12 int i,j,k;
13 
14 int main(){
15     scanf("%d",&n);
16     for(i=1;i<=n;i++){
17         scanf("%d",&in[i]);
18         maxn<in[i]?maxn=in[i]:1;
19         minn>in[i]?minn=in[i]:1;
20     }
21     maxn++,minn--;
22     maxn-=minn;
23     for(i=1;i<=n;i++) in[i]-=minn;
24     int k=0,now=0;
25     ans=in[1]+minn;
26     for(i=2;i<=n;i++,ans+=now){
27         for(j=k=in[i-1];j<maxn&&z0[j]<k;j+=j&(-j)) z0[j]=k;        
28         for(j=k=maxn-in[i-1];j<maxn&&z1[j]<k;j+=j&(-j)) z1[j]=k;        
29          for(j=in[i];j&&!z0[j];j-=j&(-j));
30         now=j==0?1<<30:in[i]-z0[j];        
31          for(j=maxn-in[i];j&&!z1[j];j-=j&(-j));
32         j&&now>maxn-in[i]-z1[j]?now=maxn-in[i]-z1[j]:1;    
33     }
34     printf("%d
",ans);
35     return 0;
36 }