洛谷P2234 [HNOI2002]營業額統計

題目描述

Tiger最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計並分析公司成立以來的營業情況。

Tiger拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當複雜的工作。由於節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況：

當最小波動值越大時，就說明營業情況越不穩定。

而分析整個公司的從成立到現在營業情況是否穩定，只需要把每一天的最小波動值加起來就可以了。你的任務就是編寫一個程式幫助Tiger來計算這一個值。

第一天的最小波動值為第一天的營業額。

該天的最小波動值=min{|該天以前某一天的營業額-該天營業額|}。

輸入輸出格式

輸入格式：

輸入由文件’turnover.in’讀入。

第一行為正整數n（n<=32767） ，表示該公司從成立一直到現在的天數，接下來的n行每行有一個整數ai(|ai|<=1000000) ，表示第i天公司的營業額，可能存在負數。

輸出格式：

輸入輸出樣例

6
5
1
2
5
4
6

12

說明

結果說明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

平衡樹的裸題

每次在前面找他的前驅

做差相加

 我這的這份可能是平衡樹里跑的最快的了

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 const int MAXN=1e6+10;
  6 const int mod=1000000;
  7 const int INF=2*0x7ffffff;
  8 inline char nc()
  9 {
 10     static char buf[MAXN],*p1=buf,*p2=buf;
 11     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin))?EOF:*p1++;
 12 }
 13 inline int read()
 14 {
 15     char c=nc();int x=0,f=1;
 16     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
 17     while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
 18     return x*f;
 19 }
 20 int PetNum;
 21 #define root tree[0].ch[1]
 22 struct node
 23 {
 24     int v,fa,ch[2],rec;
 25 }tree[MAXN];
 26 
 27 int tot,point;
 28 bool ident(int x)
 29 {
 30     return tree[tree[x].fa].ch[0]==x?0:1;
 31 }
 32 void connect(int x,int fa,int how)
 33 {
 34     tree[x].fa=fa;
 35     tree[fa].ch[how]=x;
 36 }
 37 void rotate(int x)
 38 {
 39     int Y=tree[x].fa;
 40     int R=tree[Y].fa;
 41     int Yson=ident(x);
 42     int Rson=ident(Y);
 43     int B=tree[x].ch[Yson^1];
 44     connect(B,Y,Yson);
 45     connect(Y,x,Yson^1);
 46     connect(x,R,Rson);
 47 }
 48 void splay(int x,int to)
 49 {
 50     to=tree[to].fa;
 51     while(tree[x].fa!=to)
 52     {
 53         if(tree[tree[x].fa].fa==to) rotate(x);
 54         else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);
 55         else rotate(x),rotate(x);
 56     }
 57 }
 58 void newpoint(int x,int fa)
 59 {
 60     tree[++tot].v=x;
 61     tree[tot].fa=fa;
 62     tree[tot].rec=1;
 63 }
 64 void insert(int x)
 65 {
 66     point++;
 67     if(tot==0){newpoint(x,0);root=tot;return ;}
 68     int now=root;
 69     while(1)
 70     {
 71         if(tree[now].v==x)
 72         {
 73             tree[now].rec++;
 74             splay(now,root);
 75             return ;
 76         }
 77         int nxt=x<tree[now].v?0:1;
 78         if(!tree[now].ch[nxt])
 79         {
 80             newpoint(x,now);
 81             tree[now].ch[nxt]=tot;
 82             splay(tot,root);
 83             return ;
 84         }
 85         now=tree[now].ch[nxt];
 86     }
 87 }
 88 int lower(int x)
 89 {
 90     int ans=-INF;
 91     int now=root;
 92     while(now)
 93     {
 94         if(tree[now].v<=x)   ans=max(ans,tree[now].v);
 95         int nxt=x<tree[now].v?0:1;
 96         if(tree[now].ch[nxt]==0)    return ans;
 97         now=tree[now].ch[nxt];
 98     }
 99     return ans;
100 }
101 int upper(int x)
102 {
103     int ans=INF;
104     int now=root;
105     while(now)
106     {
107         if(tree[now].v>=x)   ans=min(ans,tree[now].v);
108         int nxt=x<tree[now].v?0:1;
109         if(tree[now].ch[nxt]==0)    return ans;
110         now=tree[now].ch[nxt];
111     }
112 }
113 int main()
114 {
115     #ifdef WIN32
116     freopen("a.in","r",stdin);
117     #else
118     #endif
119     int n=read(),ans=read();
120     n=n-1;
121     insert(1<<30);
122     insert(-1<<30);
123     insert(ans);
124     while(n--)
125     {
126         int p=read();
127         int pre=lower(p);
128         int lat=upper(p);
129         ans+=min(abs(pre-p),abs(lat-p));
130         insert(p);
131     }
132     printf("%d",ans);
133 }