BZOJ 1588: [HNOI2002]营业额统计

1588: [HNOI2002]营业额统计

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 18547  Solved: 7748
[Submit][Status][Discuss]

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

12

HINT

 

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

该题数据bug已修复.----2016.5.15

 

Source

  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstdlib>
  5 #include<cmath>
  6 using namespace std;
  7  
  8 const int maxn=32767;
  9 typedef long long ll;
 10  
 11 struct node{
 12     int d,n,c,f,son[2];//d?a?μ,f?a???×μ?±ào?,c?a????μ??úμ?êy,n?aí??μμ??úμ???êy 
 13 }t[41000];
 14 int len,root;
 15  
 16 inline void update(int x)//?üD?x?ù????μ??úμ?êy 
 17 {
 18     int lc=t[x].son[0],rc=t[x].son[1];
 19     t[x].c=t[lc].c+t[rc].c+t[x].n;
 20 }
 21  
 22 inline void add(int d,int f)//ìí?ó?μ?adμ?μ?,è?f?a???×,í?ê±,fò2è??ü?ao￠×ó 
 23 {
 24     len++;
 25     t[len].d=d;
 26     t[len].n=1;
 27     t[len].c=1;
 28     t[len].f=f;
 29     if(d<t[f].d)
 30         t[f].son[0]=len;
 31     else
 32         t[f].son[1]=len;
 33     t[len].son[0]=t[len].son[1]=0;
 34 }
 35  
 36 inline void rotate(int x,int w)//×óDy(x,0)?ò??óòDy(x,1) 
 37 {
 38     int f=t[x].f,ff=t[f].f;//x?úDy×a???°,òaè·?¨xμ????×foíòˉòˉff
 39     //??à′?¨á￠1??μ 
 40     int r,R;//r′ú±í?ù±2,R±íê???±2 
 41     //óD4????é?:?òx,?òμ??ù×ó,?òμ????×,?òμ?òˉòˉ 
 42     r=t[x].son[w];R=f;//xμ??ù×ó->×?±?μ±D??ù×ó 
 43     t[R].son[1-w]=r;
 44     if(r!=0)
 45         t[r].f=R;
 46      
 47     r=x;R=ff;//x->×?±?μ±D??ù×ó 
 48     if(t[R].son[0]==f)
 49         t[R].son[0]=r;
 50     else   
 51         t[R].son[1]=r;
 52     t[r].f=R;
 53      
 54     r=f;R=x;//xμ????×->×?±?μ±D??ù×ó 
 55     t[R].son[w]=r;
 56     t[r].f=R;
 57      
 58     update(f);//?è?üD?′|óú??2?μ?μ?f 
 59     update(x);//?ù?üD?é?2?μ?x 
 60 }
 61  
 62 inline void splay(int x,int rt)//??oˉêy1|?üê??aá?è?x±?3értμ?o￠×ó(×óóò???éò?) 
 63 {
 64     while(t[x].f!=rt)//è?1?xμ?òˉòˉê?rt,???′x??DèòaDy×aò?′?(?àμ±óúì?ò?2?) 
 65     {
 66         int f=t[x].f,ff=t[f].f;
 67         if(ff==rt)
 68         {
 69             if(t[f].son[0]==x)
 70                 rotate(x,1);
 71             else
 72                 rotate(x,0);
 73         }
 74         else
 75         {
 76             if(t[ff].son[0]==f&&t[f].son[0]==x)
 77             {
 78                 rotate(f,1);rotate(x,1);
 79             }
 80             else if(t[ff].son[1]==f&&t[f].son[1]==x)
 81             {
 82                 rotate(f,0);rotate(x,0);
 83             }
 84             else if(t[ff].son[0]==f&&t[f].son[1]==x)
 85             {
 86                 rotate(x,0);rotate(x,1);
 87             }
 88             else if(t[ff].son[1]==f&&t[f].son[0]==x)
 89             {
 90                 rotate(x,1);rotate(x,0);
 91             }
 92         }
 93     }
 94     if(rt==0)
 95         root=x;
 96 }
 97  
 98 inline int findip(int d)//?ò?μ?adμ??úμ?μ??·,213?:è?1?2?′??úd,óD?é?üê??ó?üdμ?(?ò′ó?òD?)
 99 {
100     int x=root;
101     while(t[x].d!=d)
102     {
103         if(d<t[x].d)
104         {
105             if(t[x].son[0]==0)
106                 break;
107             else
108                 x=t[x].son[0];
109         }
110         else
111         {
112             if(t[x].son[1]==0)
113                 break;
114             else
115                 x=t[x].son[1];
116         }
117     }
118     return x;
119 }
120  
121 inline void insert(int d)//2?è?êy?μ?adμ?ò????úμ? 
122 {
123     if(root==0)
124     {
125         add(d,0);
126         root=len;
127         return ;
128     }
129     int x=findip(d);
130     if(t[x].d==d)
131     {
132         t[x].n++;
133         update(x);
134         splay(x,0);
135     }
136     else
137     {
138         add(d,x);
139         update(x);
140         splay(len,0);
141     }
142 }
143  
144 inline void del(int d)//é?3yêy?μ?adμ?ò????úμ? 
145 {
146     int x=findip(d);
147     splay(x,0);//?òè?,2￠?òè?yμ±ê÷?ù 
148     if(t[x].n>1)//?à??éí·Y,?í2?ó?é?μ? 
149     {
150         t[x].n--;
151         update(x);
152         return ;
153     }
154     if(t[x].son[0]==0&&t[x].son[1]==0)
155     {
156         root=0;
157         len=0;
158         return ;
159     }
160     else if(t[x].son[0]==0&&t[x].son[1]!=0)
161     {
162         root=t[x].son[1];
163         t[root].f=0;
164     }
165     else if(t[x].son[0]!=0&&t[x].son[1]==0)
166     {
167         root=t[x].son[0];
168         t[root].f=0;
169     }
170     else
171     {
172         int p=t[x].son[0];
173         while(t[p].son[1]!=0)
174             p=t[p].son[1];
175         splay(p,x);
176          
177         int r=t[x].son[1],R=p;
178          
179         t[R].son[1]=r;
180         t[r].f=R;
181          
182         root=R;
183         t[root].f=0;
184         update(R);
185     }
186 }
187  
188 inline int findrank(int d)//?ò???? 
189 {
190     int x=findip(d);
191     splay(x,0);
192     return t[t[x].son[0]].c+1;
193 }
194  
195 inline int findshuzhi(int k)//?ò?????akμ??μ 
196 {
197     int x=root;
198     while(true)
199     {
200         int lc=t[x].son[0],rc=t[x].son[1];
201         if(k<=t[lc].c) 
202             x=lc;//è￥×óo￠×ó2é?ò 
203         else if(k>t[lc].c+t[x].n)
204         {
205             k-=t[lc].c+t[x].n;
206             x=rc;
207         }//è￥óòo￠×ó2é?ò 
208         else
209             break;//?íê??? 
210     }
211     splay(x,0);
212     return x;
213 }
214  
215 inline int findqianqu(int d)//?ò?°?y 
216 {
217     int x=findip(d);
218     splay(x,0);
219     if(d<=t[x].d&&t[x].son[0]!=0) 
220     {
221         x=t[x].son[0];
222         while(t[x].son[1]!=0)
223             x=t[x].son[1];
224     }
225     if(t[x].d>=d)//è?1?ê?if(t[x].d>d)?ò?òμ?μ?ê?:D?óúμèóúdμ??°?y 
226         x=0;
227     return x;
228 }
229  
230 inline int findhouji(int d)//?òoó?ì 
231 {
232     int x=findip(d);
233     splay(x,0);
234     if(t[x].d<=d&&t[x].son[1]!=0)
235     {
236         x=t[x].son[1];
237         while(t[x].son[0]!=0)
238             x=t[x].son[0];
239     }
240     if(t[x].d<=d)
241         x=0;
242     return x;
243 }
244  
245 int main()
246 {
247     int n;
248     ll ans=0;
249     scanf("%d",&n);
250     len=0;
251     root=0;
252     for(int i=1;i<=n;i++)
253     {
254         int x;
255         scanf("%d",&x);
256         insert(x);
257         if(i==1)
258         {
259             ans+=x;
260             continue;
261         }
262         int qq=findqianqu(x),hj=findhouji(x),id=findip(x);
263         if(t[id].n>1)continue;
264         if(qq==0)
265         {
266             ans+=abs(x-t[hj].d);
267         }
268         else if(hj==0)
269         {
270             ans+=abs(x-t[qq].d);
271         }
272         else
273         {
274             ans+=min(abs(x-t[qq].d),abs(x-t[hj].d));
275         }
276     }
277     printf("%lld\n",ans);
278     return 0;
279 }