HNOI2002]营业额统计 Splay tree

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<string>
  6 #include<string.h>
  7 
  8 typedef long long ll;
  9 using namespace std;
 10 #define N 100005
 11 #define inf 1<<29
 12 int pre[N],key[N],ch[N][2],root,tot;
 13 int n;
 14 void Newnode(int &r,int fa,int k)
 15 {
 16     r=++tot;
 17     pre[r]=fa;
 18     key[r]=k;
 19     ch[r][0]=ch[r][1]=0;
 20 }
 21 void Rotate(int x,int kind)
 22 {
 23     int y=pre[x];
 24     ch[y][!kind]=ch[x][kind];
 25     pre[ch[x][kind] ]=y;
 26     if (pre[y])
 27         ch[pre[y]][ch[pre[y]][1]==y ]=x;
 28     pre[x]=pre[y];
 29     ch[x][kind ]=y;
 30     pre[y]=x;
 31 }
 32 void Splay(int r,int goal)
 33 {
 34     while(pre[r]!= goal)
 35     {
 36         if (pre[pre[r]] ==goal)
 37             Rotate(r,ch[pre[r]][0]==r);
 38         else{
 39             int y=pre[r];
 40             int kind=ch[pre[y]][0]==y;
 41 
 42             if (ch[y][kind]==r){
 43                 Rotate(r,!kind);
 44                 Rotate(r,kind);
 45             }else{
 46                 Rotate(y,kind);
 47                 Rotate(r,kind);
 48             }
 49         }
 50     }
 51     if (goal==0) root=r;
 52 }
 53 
 54 int Insert(int k)
 55 {
 56     int r=root;
 57     while (ch[r][key[r]<k]){
 58         if (key[r]==k)
 59         {
 60             Splay(r,0);
 61             return 0;
 62         }
 63         r=ch[r][key[r]<k];
 64     }
 65     Newnode(ch[r][k>key[r]],r,k);
 66     Splay(ch[r][k>key[r]],0);
 67     return 1;
 68 }
 69 
 70 int get_pre(int x){
 71     int tmp=ch[x][0];
 72     if (tmp==0) return inf;
 73     while (ch[tmp][1]) tmp=ch[tmp][1];
 74     return key[x]-key[tmp];
 75 }
 76 
 77 int get_next(int x)
 78 {
 79     int tmp=ch[x][1];
 80     if (tmp==0) return inf;
 81     while (ch[tmp][0]) tmp=ch[tmp][0];
 82     return key[tmp]-key[x];
 83 }
 84 
 85 int main()
 86 {
 87     while (scanf("%d",&n)!=EOF)
 88     {
 89         root=tot=0;
 90         int ans=0;
 91         for (int i=1;i<=n;i++)
 92         {
 93             int num;
 94             //scanf("%d",&num);
 95             if (scanf("%d",&num)==EOF) num=0;
 96             if (i==1) {
 97                 ans+=num;
 98                 Newnode(root,0,num);
 99                 continue;
100             }
101             if (Insert(num)==0) continue;
102             int a=get_next(root);
103             int b=get_pre(root);
104             ans+=min(a,b);
105         }
106         printf("%d\n",ans);
107     }
108     return 0;
109 }