bzoj1588: [HNOI2002]营业额统计(splay)

1588: [HNOI2002]营业额统计

题目：传送门

---

题解：

　　 复习splay所以来刷个水。。。

　　 题目描述不是特别清楚：应该是找第i天以前一个最小的营业额和第i天做差的最小值作为第i天的最小波动值

　　 那就直接找前驱后继啊（不过定义要改一下，是可以相同的）

　　

---

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 struct node

 {

     int d,n,c,f,son[];

 }tr[];int len,root;

 void add(int d,int f)

 {

     len++;tr[len].d=d;tr[len].n=tr[len].c=;

     tr[len].son[]=tr[len].son[]=;tr[len].f=f;

     if(d<tr[f].d)tr[f].son[]=len;

     else tr[f].son[]=len;

 }

 void update(int x)

 {

     int lc=tr[x].son[],rc=tr[x].son[];

     tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;

 }

 int findip(int d)

 {

     int x=root;

     while(tr[x].d!=d)

     {

         if(d<tr[x].d)

         {

             if(tr[x].son[]==)break;

             else x=tr[x].son[];

         }

         else

         {

             if(tr[x].son[]==)break;

             else x=tr[x].son[];

         }

     }

     return x;

 }

 void rotate(int x,int w)

 {

     int f=tr[x].f,ff=tr[f].f;

     int r,R;

     r=tr[x].son[w],R=f;

     tr[R].son[-w]=r;

     if(r!=)tr[r].f=R;

     r=x,R=ff;

     if(tr[R].son[]==f)tr[R].son[]=r;

     else                tr[R].son[]=r;

     tr[r].f=R;

     r=f,R=x;

     tr[R].son[w]=r;

     tr[r].f=R;

     update(f);update(x);

 }

 void splay(int x,int rt)

 {

     while(tr[x].f!=rt)

     {

         int f=tr[x].f,ff=tr[f].f;

         if(ff==rt)

         {

             if(tr[f].son[]==x)rotate(x,);

             else                rotate(x,);

         }

         else

         {

                  if(tr[ff].son[]==f && tr[f].son[]==x)rotate(f,),rotate(x,);

             else if(tr[ff].son[]==f && tr[f].son[]==x)rotate(f,),rotate(x,);

             else if(tr[ff].son[]==f && tr[f].son[]==x)rotate(x,),rotate(x,);

             else if(tr[ff].son[]==f && tr[f].son[]==x)rotate(x,),rotate(x,);

         }

     }

     if(rt==)root=x;

 }

 void ins(int d)

 {

     if(root==)

     {

         add(d,);root=len;

         return ;

     }

     int x=findip(d);

     if(tr[x].d==d)

     {

         tr[x].n++;

         update(x);

         splay(x,);

     }

     else

     {

         add(d,x);

         update(x);

         splay(len,);

     }

 }

 int findqianqu(int d)

 {

     int x=findip(d);splay(x,);

     if(d<tr[x].d && tr[x].son[]!=)

     {

         x=tr[x].son[];

         while(tr[x].son[]!=)x=tr[x].son[];

     }

     if(d<tr[x].d)x=;

     return x;

 }

 int findhouji(int d)

 {

     int x=findip(d);splay(x,);

     if(d>tr[x].d && tr[x].son[]!=)

     {

         x=tr[x].son[];

         while(tr[x].son[]!=)x=tr[x].son[];

     }

     if(d>tr[x].d)x=;

     return x;

 }

 int main()

 {

     int n;scanf("%d",&n);root=;

     int ans=;int d;

     scanf("%d",&d);ans+=d;ins(d);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&d);int ss=;

         int lc=findqianqu(d),rc=findhouji(d);

         if(lc!=)ss=abs(tr[lc].d-d);

         if(rc!=)ss=min(abs(tr[rc].d-d),ss);

         ans+=ss;ins(d);

     }

     printf("%d\n",ans);

     return ;

 }