首页 > 代码库 > 3223: Tyvj 1729 文艺平衡树
3223: Tyvj 1729 文艺平衡树
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
1 3
1 3
1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
Source
平衡树
题解：一道经典的区间反转问题（既然网上的各个解说大多不尽详细，那么就由我来重复一遍吧么么哒）——如题目的Source所言，这里面要用到splay树（但是个人对平衡树这一定义持怀疑态度——毕竟平衡树是二叉查找树，当你区间反转来反转去后还符合二叉查找树的性质么？）首先把区间的右界再往右一个的点splay到树顶，然后把左界再往左一个的点splay到树顶的子树位置（详见我的过程splay2），这样子此子树根的右子树则刚刚好由我们所需要反转的节点构成，起初我一个个一层层反转，于是不出所料——程序运行速度还没有O(n^2)的暴力快（phile：那不是显然的么 HansBug：TT）于是我们的重头戏——lazytag上场——这里面的懒标记可以类比线段树里面的，它需要支持一个向下扩展的操作（详见过程ext），即反转此点左右子树，然后把标记蔓延到左右子树上，自己的标记解除，然后注意的是每次左转或者右转节点时需要保证关键的节点先去除掉lazytag，求第N号节点、最终求序列时也是如此，然后很嗨皮的AC么么哒（HansBug：代码太长求原谅TT）
1 var 2 i,j,k,l,m,n,head,a1,a2:longint; 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 begin100 lt(fat[fat[x]]);101 lt(fat[x]);102 end103 else104 begin105 lt(fat[x]);106 rt(fat[x]);107 end;108 end;109 end;110 procedure up1(x:longint);inline;111 begin112 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 begin117 if (x=0) or (fat[x]=0) then exit;118 while fat[fat[x]]>0 do119 up2(x);120 if fat[x]>0 then up2(x);121 head:=x;122 end;123 procedure splay2(x:longint);inline;124 begin125 if (x=0) or (fat[x]=0) then exit;126 while fat[fat[fat[x]]]>0 do127 up2(x);128 if fat[fat[x]]>0 then up1(x);129 end;130 function getrank(x,y:longint):longint;inline;131 begin132 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 begin140 if (x=1) and (y=n) then141 c[head]:=1-c[head]142 else143 begin144 if (x=1) then145 begin146 a1:=getrank(head,y+1);147 splay(a1);148 ext(a1);149 c[lef[a1]]:=1-c[lef[a1]];150 end151 else152 begin153 if (y=n) then154 begin155 a2:=getrank(head,x-1);156 splay(a2);157 ext(a2);158 c[rig[a2]]:=1-c[rig[a2]];159 end160 else161 begin162 a1:=getrank(head,x-1);163 a2:=getrank(head,y+1);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 begin174 if x=0 then exit(‘‘);175 ext(x);176 str(x,s1);177 exit(showoff(lef[x])+s1+‘ ‘+showoff(rig[x]));178 end;179 begin180 readln(n,m);181 for i:=1 to n do182 begin183 a[i]:=i;c[i]:=0;b[i]:=1;184 end;185 head:=1;186 for i:=2 to n do187 begin188 ins(head,i);189 splay(random(i)+1);190 end;191 for i:=1 to m do192 begin193 readln(a1,a2);194 turn(a1,a2);195 end;196 s1:=showoff(head);197 writeln(s1);198 readln;199 end.200
3223: Tyvj 1729 文艺平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。