1 program Xiong;
2 var
3 count,father,data:
array[
0..
10000]
of longint;
4 son:
array[
0..
10000,
0..
1]
of longint;
5 root,n,m,t,i:longint;
6
7 procedure rotate(x,how:longint);
8 var
9 up,uup:longint;
10 begin
11 up:=
father[x];
12 uup:=
father[up];
13
14 count[up]:=count[up]+count[son[x,how]]-
count[x];
15 count[x]:=count[x]-count[son[x,how]]+
count[up];
16
17 father[x]:=
uup;
18 father[up]:=
x;
19 if son[x,how]<>
0 then father[son[x,how]]:=
up;
20
21 son[up,
1-how]:=
son[x,how];
22 son[x,how]:=
up;
23 if uup<>
0 then
24 if up=son[uup,
0]
then
25 son[uup,
0]:=
x
26 else
27 son[uup,
1]:=
x;
28 end;
29
30 procedure splay(x,des:longint);
31 begin
32 while father[x]<>des
do
33 if father[father[x]]=des
then
34 if x=son[father[x],
0]
then
35 rotate(x,
1)
36 else
37 rotate(x,
0)
38 else
39 if x=son[father[x],
0]
then
40 if father[x]=son[father[father[x]],
0]
then begin
41 rotate(father[x],
1);
42 rotate(x,
1);
43 end else begin
44 rotate(x,
1);
45 rotate(x,
0);
46 end
47 else
48 if father[x]=son[father[father[x]],
1]
then begin
49 rotate(father[x],
0);
50 rotate(x,
0);
51 end else begin
52 rotate(x,
0);
53 rotate(x,
1);
54 end;
55 if des=
0 then root:=
x;
56 end;
57
58 procedure insert(m:longint);
59 var
60 now:longint;
61 begin
62 inc(t);
63 data[t]:=
m;
64 now:=
root;
65 while (son[now,
0]<>
0)
and(data[t]<=data[now])
or(son[now,
1]<>
0)
and(data[t]>data[now])
do begin
66 inc(count[now]);
67 if data[t]<=data[now]
then
68 now:=son[now,
0]
69 else
70 now:=son[now,
1];
71 end;
72 if now<>
0 then begin
73 inc(count[now]);
74 if data[t]<=data[now]
then begin
75 son[now,
0]:=
t;
76 father[t]:=
now;
77 end else begin
78 son[now,
1]:=
t;
79 father[t]:=
now;
80 end;
81 end;
82 count[t]:=
1;
83 splay(t,
0);
84 end;
85
86 function find(m:longint):longint;
87 var
88 now:longint;
89 begin
90 now:=
root;
91 while (data[now]<>m)
and(now<>
0)
do
92 if data[now]>m
then
93 now:=son[now,
0]
94 else
95 now:=son[now,
1];
96 exit(now);
97 end;
98
99 procedure delete(m:longint);
100 var
101 pos,prev,next:longint;
102 begin
103 pos:=
find(m);
104 if pos<>
0 then begin
105 splay(pos,
0);
106 prev:=son[root,
0];
107 while son[prev,
1]<>
0 do
108 prev:=son[prev,
1];
109 next:=son[root,
1];
110 while son[next,
0]<>
0 do
111 next:=son[next,
0];
112 if prev<>
0 then
113 if next<>
0 then begin
114 splay(prev,
0);
115 splay(next,root);
116 son[next,
0]:=
0;
117 dec(count[next]);
118 dec(count[prev]);
119 end else begin
120 splay(prev,
0);
121 son[prev,
1]:=
0;
122 dec(count[prev]);
123 end
124 else
125 if next<>
0 then begin
126 splay(next,
0);
127 son[next,
0]:=
0;
128 dec(count[next]);
129 end else
130 root:=
0;
131 father[pos]:=
0;
132 end;
133 end;
134
135 procedure all(m:longint);
136 begin
137 if son[m,
0]<>
0 then
138 all(son[m,
0]);
139 write(data[m],
' ');
140 if son[m,
1]<>
0 then
141 all(son[m,
1]);
142 end;
143
144 begin
145 assign(input,
'input.txt');reset(input);
146 assign(output,
'output.txt');rewrite(output);
147
148 read(n);
149 for i:=
1 to n
do begin
150 read(m);
151 insert(m);
152 end;
153
154 delete(
5);
155 all(root);
156
157 close(input);
158 close(output);
159 end.
这个还算是比较漂亮了吧，我已经尽量精简了……毕竟第一次写，还会改进嗯！！
转载于:https://www.cnblogs.com/xiong298/archive/2012/04/29/2476303.html
