实现功能:同splay区间反转 1(基于BZOJ3223 文艺平衡树)
这次改用了一个全新的模板(HansBug:琢磨了我大半天啊有木有),大大简化了程序,同时对于splay的功能也有所完善
这里面没有像一般二叉排序树那样子用一个参量进行排序,而是直接以中序遍历来构建了一个普通的二叉树(当然也可以把每个点的中序遍历排名视作参量),然后插入的时候就是指定位置插入(这个就比较像是文本插入了)
总之得到了较大的提升,代码优美程度也提高不少
1 var
2 i,j,k,l,m,n,head,tot,ll:longint;
3 a,lef,rig,b,c:array[0..100000] of longint;
4 procedure swap(var x,y:longint);
5 var z:longint;
6 begin
7 z:=x;x:=y;y:=z;
8 end;
9 procedure ext(x:longint); //经典的下推操作,有木有很像线段树呢= =
10 begin
11 if x=0 then exit;
12 if c[x]=0 then exit;
13 if lef[x]<>0 then c[lef[x]]:=1-c[lef[x]];
14 if rig[x]<>0 then c[rig[x]]:=1-c[rig[x]];
15 swap(lef[x],rig[x]);
16 c[x]:=0;
17 end;
18 procedure rt(var x:longint); //lt、rt函数和Treap的极其相似!!!
19 var f,l:longint;
20 begin
21 ext(x);ext(lef[x]);
22 if (x=0) or (lef[x]=0) then exit;
23 f:=x;l:=lef[x];
24 b[lef[x]]:=b[x];
25 b[x]:=1+b[rig[x]]+b[rig[lef[x]]];
26 lef[f]:=rig[l];
27 rig[l]:=f;
28 x:=l;
29 end;
30 procedure lt(var x:longint);
31 var f,r:longint;
32 begin
33 ext(x);ext(rig[x]);
34 if (x=0) or (rig[x]=0) then exit;
35 f:=x;r:=rig[x];
36 b[rig[x]]:=b[x];
37 b[x]:=1+b[lef[x]]+b[lef[rig[x]]];
38 rig[f]:=lef[r];
39 lef[r]:=f;
40 x:=r;
41 end;
42 procedure splay(var head:longint;x:longint); //萌萌哒伸展——而且还可以支持伸展的任意位置,只要设定head的位置,比如像后面的splay(rig[head],x);
43 begin
44 if head=0 then exit;
45 ext(head);
46 if (b[lef[head]]+1)=x then exit;
47 if x<(b[lef[head]]+1) then
48 begin
49 ext(lef[head]);
50 if x=(b[lef[lef[head]]]+1) then rt(head) else
51 if x<(b[lef[lef[head]]]+1) then
52 begin
53 splay(lef[lef[head]],x);
54 rt(head);rt(head);
55 end
56 else
57 begin
58 splay(rig[lef[head]],x-1-b[lef[lef[head]]]);
59 lt(lef[head]);rt(head);
60 end;
61 end
62 else
63 begin
64 ext(rig[head]);
65 x:=x-1-b[lef[head]];
66 if x=(b[lef[rig[head]]]+1) then lt(head) else
67 if x<(b[lef[rig[head]]]+1) then
68 begin
69 splay(lef[rig[head]],x);
70 rt(rig[head]);lt(head);
71 end
72 else
73 begin
74 splay(rig[rig[head]],x-1-b[lef[rig[head]]]);
75 lt(head);lt(head);
76 end;
77 end;
78 end;
79 procedure ins(x,y:longint); //这里的ins操作已经可以支持指定位置插入子伸展树了
80 begin
81 if head=0 then
82 begin
83 head:=y;
84 exit;
85 end;
86 if x=b[head] then
87 begin
88 splay(head,b[head]);
89 rig[head]:=y;
90 inc(b[head],b[y]);
91 end
92 else if x=0 then
93 begin
94 splay(head,1);
95 lef[head]:=y;
96 inc(b[head],b[y]);
97 end
98 else begin
99 splay(head,x);
100 splay(rig[head],x+1);
101 lef[rig[head]]:=y;
102 inc(b[rig[head]],b[y]);
103 inc(b[head],b[y]);
104 end;
105 end;
106 procedure putinvalue(x,y:longint); //加入单个值
107 begin
108 inc(tot);
109 A[TOT]:=x;b[tot]:=1;
110 lef[tot]:=0;rig[tot]:=0;
111 ins(y,tot);
112 end;
113
114 procedure turnover(x,y:longint); //翻转,核心思想还是打标记
115 begin
116 if x=y then exit;
117 if (x=1) and (y=n) then
118 begin
119 c[head]:=1-c[head];
120 exit;
121 end;
122 if (x=1) then
123 begin
124 splay(head,y+1);
125 c[lef[head]]:=1-c[lef[head]];
126 end
127 else if (y=n) then
128 begin
129 splay(head,x-1);
130 c[rig[head]]:=1-c[rig[head]];
131 end
132 else begin
133 splay(head,x-1);
134 splay(rig[head],y-x+2);
135 c[lef[rig[head]]]:=1-c[lef[rig[head]]];
136 end;
137 end;
138 function showtree(head:longint):ansistring;
139 var s1,s2,s3,s4:ansistring;
140 begin
141 if head=0 then exit('');
142 str(a[head],s1);
143 s2:=showtree(lef[head]);
144 s3:=showtree(rig[head]);
145 if c[head]=1 then
146 begin
147 s4:=s2;
148 s2:=s3;
149 s3:=s4;
150 end;
151 if s3<>'' then s3:=','+s3;
152 s2:=s2+s3;
153 if s2<>'' then s2:='('+s2+')';
154 exit(s1+s2);
155 end;
156 procedure putout(x:longint);
157 begin
158 if x=0 then exit;
159 ext(x);
160 putout(lef[x]);
161 write(a[x],' ');
162 putout(rig[x]);
163 end;
164 begin
165 readln(n,m);head:=0;tot:=0;
166 for i:=1 to n do putinvalue(i,i-1);
167 fillchar(c,sizeof(c),0);
168 for i:=1 to m do
169 begin
170 readln(j,k);
171 turnover(j,k);
172 l:=0;
173
174 end;
175 putout(head);
176 writeln;
177 readln;
178 end.