# 算法模板——splay区间反转 1

```  1 var
3    s1:ansistring;
4    a,b,c,d,fat,lef,rig:array[0..200000] of longint;
5 procedure swap(var x,y:longint);inline;
6           var z:longint;
7           begin
8                z:=x;x:=y;y:=z;
9           end;
10
11 procedure ext(x:longint);inline;
12           begin
13                if (x=0) then exit;
14                if c[x]=0 then exit;
15                swap(lef[x],rig[x]);
16                c[x]:=0;
17                c[lef[x]]:=1-c[lef[x]];
18                c[rig[x]]:=1-c[rig[x]];
19                c[0]:=0;
20           end;
21 procedure rt(x:longint);inline;
22           var f,l:longint;
23           begin
24                if x=0 then exit;
25                ext(x);
26                if lef[x]=0 then exit;
27                ext(lef[x]);
28                f:=x;l:=lef[x];
29                b[lef[x]]:=b[x];
30                b[x]:=b[rig[x]]+1+b[rig[l]];
31                lef[x]:=rig[l];
32                fat[rig[l]]:=x;
33                rig[l]:=x;
34                fat[l]:=fat[x];
35                fat[x]:=l;
36                if rig[fat[l]]=x then rig[fat[l]]:=l;
37                if lef[fat[l]]=x then lef[fat[l]]:=l;
38                fat[0]:=0;
39           end;
40 procedure lt(x:longint);inline;
41           var f,r:longint;
42           begin
43                if x=0 then exit;
44                ext(x);if rig[x]=0 then exit;
45                ext(rig[x]);
46                f:=x;r:=rig[x];
47                b[rig[x]]:=b[x];
48                b[x]:=1+b[lef[x]]+b[lef[r]];
49                rig[x]:=lef[r];
50                fat[lef[r]]:=x;
51                lef[r]:=x;
52                fat[r]:=fat[x];
53                fat[x]:=r;
54                if rig[fat[r]]=x then rig[fat[r]]:=r;
55                if lef[fat[r]]=x then lef[fat[r]]:=r;
56                fat[0]:=0;
57           end;
58 procedure ins(x,y:longint);inline;
59           begin
60                if a[y]<a[x] then
61                   begin
62                        if lef[x]=0 then
63                           begin
64                                lef[x]:=y;
65                                fat[y]:=x;
66                           end
67                        else ins(lef[x],y);
68                   end
69                else
70                    begin
71                         if rig[x]=0 then
72                            begin
73                                 rig[x]:=y;
74                                 fat[y]:=x;
75                            end
76                         else ins(rig[x],y);
77                    end;
78                b[x]:=1+b[lef[x]]+b[rig[x]];
79           end;
80 procedure up2(var x:longint);inline;
81           begin
82                if (fat[x]=0) or (x=0) then exit;
83                if lef[fat[x]]=x then
84                   begin
85                        if lef[fat[fat[x]]]=fat[x] then
86                           begin
87                                rt(fat[fat[x]]);
88                                rt(fat[x]);
89                           end
90                        else
91                            begin
92                                 rt(fat[x]);
93                                 lt(fat[x]);
94                            end;
95                   end
96                else
97                    begin
98                         if rig[fat[fat[x]]]=fat[x] then
99                            begin
100                                 lt(fat[fat[x]]);
101                                 lt(fat[x]);
102                            end
103                         else
104                             begin
105                                  lt(fat[x]);
106                                  rt(fat[x]);
107                             end;
108                    end;
109           end;
110 procedure up1(x:longint);inline;
111           begin
112                if (x=0) or (fat[x]=0) then exit;
113                if lef[fat[x]]=x then rt(fat[x]) else lt(fat[x]);
114           end;
115 procedure splay(x:longint);inline;
116           begin
117                if (x=0) or (fat[x]=0) then exit;
118                while fat[fat[x]]>0 do
119                      up2(x);
120                if fat[x]>0 then up2(x);
122           end;
123 procedure splay2(x:longint);inline;
124           begin
125                if (x=0) or (fat[x]=0) then exit;
126                while fat[fat[fat[x]]]>0 do
127                      up2(x);
128                if fat[fat[x]]>0 then up1(x);
129           end;
130 function getrank(x,y:longint):longint;inline;
131          begin
132               if (x=0) then exit(0);
133               ext(x);
134               if (b[lef[x]]+1)=y then exit(x);
135               if (b[lef[x]]+1)>y then exit(getrank(lef[x],y)) else exit(getrank(rig[x],y-1-b[lef[x]]));
136          end;
137 procedure turn(x,y:longint);inline;
138           var a1,a2:longint;
139           begin
140                if (x=1) and (y=n) then
142                else
143                    begin
144                         if (x=1) then
145                            begin
147                                 splay(a1);
148                                 ext(a1);
149                                 c[lef[a1]]:=1-c[lef[a1]];
150                            end
151                         else
152                             begin
153                                  if (y=n) then
154                                     begin
156                                          splay(a2);
157                                          ext(a2);
158                                          c[rig[a2]]:=1-c[rig[a2]];
159                                     end
160                                  else
161                                      begin
164                                           splay(a2);splay2(a1);
165                                           ext(a2);ext(a1);
166                                           c[rig[a1]]:=1-c[rig[a1]];
167                                      end;
168                             end;
169                    end;
170           end;
171 function showoff(x:longint):ansistring;inline;
172          var s1:ansistring;
173          begin
174               if x=0 then exit('');
175               ext(x);
176               str(x,s1);
177               exit(showoff(lef[x])+s1+' '+showoff(rig[x]));
178          end;
179 begin
181      for i:=1 to n do
182          begin
183               a[i]:=i;c[i]:=0;b[i]:=1;
184          end;
186      for i:=2 to n do
187          begin
189               splay(random(i)+1);
190          end;
191      for i:=1 to m do
192          begin
194               turn(a1,a2);
195          end;
197      writeln(s1);
199 end.
200                   ```

251 篇文章37 人订阅

0 条评论