Splay tree入门题，学好代码风格，学习HH大牛的，传送门。。
1 #include <functional> 2 #include <algorithm> 3 #include <iostream> 4 //#include <ext/rope> 5 #include <fstream> 6 #include <sstream> 7 #include <iomanip> 8 #include <numeric> 9 #include <cstring> 10 #include <cassert> 11 #include <cstdio> 12 #include <string> 13 #include <vector> 14 #include <bitset> 15 #include <queue> 16 #include <stack> 17 #include <cmath> 18 #include <ctime> 19 #include <list> 20 #include <set> 21 #include <map> 22 using namespace std; 23 //using namespace __gnu_cxx; 24 //define 25 #define pii pair<int,int> 26 #define mem(a,b) memset(a,b,sizeof(a)) 27 #define lson l,mid,rt<<1 28 #define rson mid+1,r,rt<<1|1 29 #define PI acos(-1.0) 30 //typedef 31 typedef long long LL; 32 typedef unsigned long long ULL; 33 //const 34 const int N=100005; 35 const int INF=0x3f3f3f3f; 36 const int MOD=100000,STA=8000010; 37 const LL LNF=1LL<<60; 38 const double EPS=1e-8; 39 const double OO=1e15; 40 const int dx[4]={-1,0,1,0}; 41 const int dy[4]={0,1,0,-1}; 42 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; 43 //Daily Use ... 44 inline int sign(double x){return (x>EPS)-(x<-EPS);} 45 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;} 46 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} 47 template<class T> inline T lcm(T a,T b,T d){return a/d*b;} 48 template<class T> inline T Min(T a,T b){return a<b?a:b;} 49 template<class T> inline T Max(T a,T b){return a>b?a:b;} 50 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);} 51 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);} 52 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));} 53 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));} 54 //End 55 56 int pre[N],key[N],ch[N][2],root,tot; //分别表示父结点，键值，左右孩子(0为左孩子，1为右孩子),根结点，结点数量 57 int n; 58 //新建一个结点 59 void addn(int &r,int fa,int k) 60 { 61 r=++tot; 62 pre[r]=fa; 63 key[r]=k; 64 ch[r][0]=ch[r][1]=0; //左右孩子为空 65 } 66 //旋转，kind为1为右旋，kind为0为左旋 67 int Rotate(int x,int kind) 68 { 69 int y=pre[x],z=pre[y]; 70 //类似SBT，要把其中一个分支先给父节点 71 ch[y][!kind]=ch[x][kind]; 72 pre[ch[x][kind]]=y; 73 //如果父节点不是根结点，则要和父节点的父节点连接起来 74 if(z)ch[z][ch[z][1]==y]=x; 75 pre[x]=z; 76 ch[x][kind]=y; 77 pre[y]=x; 78 } 79 //Splay调整，将根为r的子树调整为goal 80 int Splay(int r,int goal) 81 { 82 int y,kind; 83 while(pre[r]!=goal){ 84 //父节点即是目标位置，goal为0表示，父节点就是根结点 85 y=pre[r]; 86 if(pre[y]==goal){ 87 Rotate(r,ch[y][0]==r); 88 } 89 else { 90 kind=ch[pre[y]][0]==y; 91 //两个方向不同，则先左旋再右旋 92 if(ch[y][kind]==r){ 93 Rotate(r,!kind); 94 Rotate(r,kind); 95 } 96 //两个方向相同，相同方向连续两次 97 else { 98 Rotate(y,kind); 99 Rotate(r,kind); 100 } 101 } 102 } 103 //更新根结点 104 if(goal==0)root=r; 105 } 106 107 int Insert(int k) 108 { 109 int r=root; 110 while(ch[r][k>key[r]]){ 111 //不重复插入 112 if(key[r]==k){ 113 Splay(r,0); 114 return 0; 115 } 116 r=ch[r][k>key[r]]; 117 } 118 addn(ch[r][k>key[r]],r,k); 119 //将新插入的结点更新至根结点 120 Splay(ch[r][k>key[r]],0); 121 return 1; 122 } 123 //找前驱，即左子树的最右结点 124 int getpre(int x) 125 { 126 if(!ch[x][0])return -INF; 127 x=ch[x][0]; 128 while(ch[x][1])x=ch[x][1]; 129 return key[x]; 130 } 131 //找后继，即右子树的最左结点 132 int getsuf(int x) 133 { 134 if(!ch[x][1])return INF; 135 x=ch[x][1]; 136 while(ch[x][0])x=ch[x][0]; 137 return key[x]; 138 } 139 140 int main() 141 { 142 // freopen("in.txt","r",stdin); 143 int i,a,ans; 144 while(~scanf("%d",&n)) 145 { 146 ans=root=tot=0; 147 for(i=0;i<n;i++){ 148 if(scanf("%d",&a)==EOF)a=0; 149 if(i==0){ 150 ans+=a; 151 addn(root,0,a); 152 } 153 else { 154 if(Insert(a)==0)continue; 155 ans+=Min(a-getpre(root),getsuf(root)-a); 156 } 157 } 158 printf("%d ",ans); 159 } 160 return 0; 161 }