首页 > 代码库 > bzoj2843极地旅行社
bzoj2843极地旅行社
Description
不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服
务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko的旅行社遭受一次
重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望
开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些
岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0
, 1000]之间。你的程序需要处理以下三种命令：
1."bridge A B"——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当
A与B不联通。若这项命令被接受，你的程序需要输出"yes"，之
后会建造这座大桥。否则，你的程序需要输出"no"。
2."penguins A X"——根据可靠消息，岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的，你的程序不
需要回应。
3."excursion A B"——一个旅行团希望从A出发到B。若A与B连通，你的程序需要输出这个旅行团一路上所能看到的
帝企鹅数量（包括起点A与终点B），若不联通，你的程序需要输出"impossible"。
Input
第一行一个正整数N，表示冰岛的数量。
第二行N个范围[0, 1000]的整数，为每座岛屿初始的帝企鹅数量。
第三行一个正整数M，表示命令的数量。接下来M行即命令，为题目描述所示。
1<=N<=30000,1<=M<=100000
Output
对于每个bridge命令与excursion命令，输出一行，为题目描述所示。
Sample Input
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
Sample Output
4
impossible
yes
6
yes
yes
15
yes
15
16
impossible
yes
6
yes
yes
15
yes
15
16
题解：
LCT练习题，因为没有cut操作，可以离线用树链剖分+并查集搞。
代码：
1 var 2 i,j,k,l,n,m,dts,y,a,b:longint; 3 fa,sm,v,rev,dt:array[0..50001]of longint; 4 ch:array[0..50001,0..1]of longint; 5 ch1,ch2:char; 6 procedure update(x:longint); 7 begin 8 if x=0 then exit; sm[x]:=v[x]; 9 if ch[x,0]<>0 then sm[x]:=sm[x]+sm[ch[x,0]]; 10 if ch[x,1]<>0 then sm[x]:=sm[x]+sm[ch[x,1]]; 11 end; 12 function isroot(x:longint):boolean; 13 begin 14 if(x=0)or(fa[x]=0)then exit(true); 15 exit((x<>ch[fa[x],0])and(x<>ch[fa[x],1])); 16 end; 17 procedure pushdown(x:longint); 18 var tt:longint; 19 begin 20 if rev[x]=1 then 21 begin 22 tt:=ch[x,1]; ch[x,1]:=ch[x,0]; ch[x,0]:=tt; rev[x]:=0; 23 if ch[x,0]<>0 then rev[ch[x,0]]:=rev[ch[x,0]]xor 1; 24 if ch[x,1]<>0 then rev[ch[x,1]]:=rev[ch[x,1]]xor 1; 25 end; 26 end; 27 procedure rotate(x:longint); 28 var a1,a2,a3,b1,b2,b3:longint; 29 begin 30 if(x=0)or(isroot(x))then exit; 31 a1:=fa[x]; a2:=fa[fa[x]]; 32 if x=ch[a1,1] then b1:=1 else b1:=0; 33 if a1=ch[a2,1] then b2:=1 else b2:=0; 34 if isroot(a1)then b3:=1 else b3:=0; a3:=ch[x,1-b1]; 35 if b3=0 then ch[a2,b2]:=x; fa[x]:=a2; ch[a1,b1]:=a3; 36 if a3>0 then fa[a3]:=a1; ch[x,1-b1]:=a1; fa[a1]:=x; 37 update(a1); update(x); if b3=0 then update(a2); 38 end; 39 procedure splay(x:longint); 40 begin 41 if x=0 then exit; dts:=0; y:=x; 42 while not isroot(y) do begin inc(dts); dt[dts]:=y; y:=fa[y]; end; 43 inc(dts); dt[dts]:=y; while dts>0 do begin pushdown(dt[dts]); dec(dts); end; 44 while not isroot(x) do 45 begin 46 if not isroot(fa[x]) then 47 begin 48 if(x=ch[fa[x],1])xor(fa[x]=ch[fa[fa[x]],1]) 49 then rotate(x) else rotate(fa[x]); 50 end; 51 rotate(x); 52 end; 53 end; 54 function access(x:longint):longint; 55 var t:longint; 56 begin 57 if x=0 then exit(0); t:=0; 58 while x>0 do 59 begin 60 splay(x); ch[x,1]:=t; update(x); 61 if t>0 then fa[t]:=x; t:=x; x:=fa[x]; 62 end; 63 exit(t); 64 end; 65 procedure cut(x,y:longint); 66 begin 67 if(x=0)and(y=0)then exit; 68 access(x); splay(x); rev[x]:=rev[x]xor 1; 69 access(y); splay(x); fa[y]:=0; ch[x,1]:=0; update(x); 70 end; 71 procedure link(x,y:longint); 72 begin 73 if(x=0)and(y=0)then exit; 74 access(x); splay(x); rev[x]:=rev[x]xor 1; fa[x]:=y; 75 end; 76 function qsum(x,y:longint):longint; 77 var a:longint; 78 begin 79 if(x=0)or(y=0)then exit(0); if x=y then exit(v[x]); 80 access(x); a:=access(y); splay(x); 81 if x=a then exit(v[a]+sm[ch[a,1]])else exit(sm[x]+v[a]+sm[ch[a,1]]); 82 end; 83 procedure change(x,y:longint); 84 begin 85 splay(x); v[x]:=y; update(x); 86 end; 87 function find(x:longint):longint; 88 begin 89 access(x); splay(x); while ch[x,0]>0 do x:=ch[x,0]; exit(x); 90 end; 91 begin 92 readln(n); for i:=1 to n do read(v[i]); sm[i]:=v[i]; readln(m); 93 for i:=1 to m do 94 begin 95 read(ch1); read(ch2); while ch2<>‘ ‘ do read(ch2); readln(a,b); 96 if ch1=‘b‘ then 97 begin 98 if find(a)=find(b) then writeln(‘no‘)else 99 begin writeln(‘yes‘); link(a,b); end; 100 end else if ch1=‘p‘ then change(a,b) else 101 if find(a)<>find(b) then writeln(‘impossible‘)else writeln(qsum(a,b)); 102 end; 103 end.
bzoj2843极地旅行社
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。