bzoj 1588売上高統計
treapを出します.一番近い二つの前のポイントを探して計算すればいいです.友達から私のコードのスタイルは黄先輩に似ています.そうです.私は彼のコードのスタイルを勉強しています.
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define N 50005
#define inf 10000000
using namespace std;
int ls[N],rs[N],ra[N],key[N],siz[N],root,len;
int n,ans,t1,t2;
void push(int k)
{
siz[k]=siz[ls[k]]+siz[rs[k]]+1;
}
void rturn(int &k)
{
int t=ls[k];
ls[k]=rs[t];
rs[t]=k;
siz[t]=siz[k];
push(k);
k=t;
}
void lturn(int &k)
{
int t=rs[k];
rs[k]=ls[t];
ls[t]=k;
siz[t]=siz[k];
push(k);
k=t;
}
void ins(int &k,int val)
{
if (!k)
{
int t=++len;
key[t]=val;
siz[t]=1;
ra[t]=rand();
k=t;
return;
}
siz[k]++;
if (val>=key[k])
{
ins(rs[k],val);
if (ra[rs[k]]<ra[k]) lturn(k);
}
else
{
ins(ls[k],val);
if (ra[ls[k]]<ra[k]) rturn(k);
}
}
void askbefore(int k,int val)
{
if (!k) return;
if (key[k]<=val)
{
t1=key[k];
askbefore(rs[k],val);
}
else askbefore(ls[k],val);
}
void askafter(int k,int val)
{
if (!k) return;
if (key[k]>=val)
{
t2=key[k];
askafter(ls[k],val);
}
else askafter(rs[k],val);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
if(scanf("%d",&x)==EOF)x=0;
t1=-inf,t2=inf;
askbefore(root,x);
askafter(root,x);
if (i!=1) ans+=min(x-t1,t2-x);
else ans+=x;
ins(root,x);
// printf("%d %d %d %d
",t1,t2,x,ans);
}
printf("%d",ans);
return 0;
}