[文章目录]
Description
Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：
当最小波动值越大时，就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。
第一天的最小波动值为第一天的营业额。
说好的0<ai<=1000000呢，啊啊啊啊啊，我日。
加了1000000才过。
两种解法，第一种，平衡树。（我的splay被JDOI卡了，BZOJ过了。啊啊啊）
维护一个单调数列，logn找前驱后继+插入。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,ans;
struct node
{
node *fa,*c[2];
int siz,val;
node(int x);
void pushup() {siz=c[0]->siz+c[1]->siz+1;}
}*null=new node(0),*root;
node::node(int x)
{
fa=c[0]=c[1]=null;
siz=null?1:0;
val=x;
}
inline int Abs(int x) {return x>0?x:-x;}
void initialize()
{
root=new node(-1<<30);
root->c[1]=new node(1<<30);
root->c[1]->fa=root;
root->pushup();
}
void rotate(node *x)
{
node *y=x->fa;int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r];x->c[r]->fa=y;
x->c[r]=y;x->fa=y->fa;
if(y==y->fa->c[0]) y->fa->c[0]=x;
else y->fa->c[1]=x;
y->fa=x;y->pushup();x->pushup();
if(y==root) root=x;
}
void splay(node *x,node *tar)
{
for(node *y;(y=x->fa)!=tar;rotate(x))
if(y->fa!=tar)
rotate((y==y->fa->c[0])^(x==y->c[0]) ? y:x);
}
void insert(int x)
{
root->c[1]->c[0]=new node(x);
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->pushup();
root->pushup();
}
void find(int x)
{
node *y=root,*z;
while(y!=null)
{
if(y->val<=x) z=y,y=y->c[1];
else y=y->c[0];
}
splay(z,null);
y=root->c[1];
while(y->c[0]!=null) y=y->c[0];
splay(y,root);
ans+=min(Abs(root->val-x),Abs(root->c[1]->val-x));
}
int main()
{
initialize();
scanf("%d",&n);n--;
int tmp;
scanf("%d",&tmp);
ans+=tmp;insert(tmp);
while(n--)
{
int tmp;
scanf("%d",&tmp);
find(tmp);
insert(tmp);
}
printf("%d",ans);
return 0;
}第二种方法，权值树状数组，维护前缀最大权值和后缀最小权值（前缀只能改大，后缀只能改小）。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000000
int mi[2010000],mx[2010000],n,now,ans;
bool v[2010000];
inline int Abs(int x)
{return x>0?x:-x;}
void fix(const int x)
{
for(int i=x;i<=2000000;i+=-i&i)
mi[i]=max(mi[i],x);
for(int i=x;i>0;i-=-i&i)
mx[i]=min(mx[i],x);
}
void query(const int x)
{
int re=-1<<30,fna;
for(int i=x;i>0;i-=-i&i)
re=max(re,mi[i]);
fna=Abs(x-re);re=1<<30;
for(int i=x;i<=2000000;i+=-i&i)
re=min(re,mx[i]);
fna=min(fna,Abs(x-re));
ans+=fna;
}
int main()
{
memset(mx,0x3f,sizeof(mx));
memset(mi,0xef,sizeof(mi));
scanf("%d",&n);n--;
scanf("%d",&now);
ans=now;v[now+N]=1;fix(now+N);
while(n--)
{
scanf("%d",&now);
if(v[now+N]) continue;
v[now+N]=1;
query(now+N);
fix(now+N);
}
printf("%d",ans);
return 0;
}