首页 > 代码库 > BZOJ4530[BJOI2014]大融合
BZOJ4530[BJOI2014]大融合
Description
小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。
这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够
联通的树上路过它的简单路径的数量。
例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因
为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。
现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的
询问。
Input
第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。
接下来的Q行，每行是如下两种格式之一：
A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。
Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。
1≤N,Q≤100000
Output
对每个查询操作，输出被查询的边的负载。
Sample Input
8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8
Sample Output
6
题解：
刚听jiry_2讲了线段树合并，于是找了这一题来做。听说可以用LCT做，不在乎
先把最终的树（或是森林）建出来，求一次DFS序。
一开始，每个节点都是一个联通块，对应一棵以DFS序作为下标的线段树，将其对应DFS序插入该线段树中
连边时，用并查集维护联通块合并，记录大小，并合并两棵线段树。
询问时，找到两点中深度较深的一个，求出其DFS子树中有几个点在联通块中（即求所在联通块对应的线段树的区间和），设联通块有x个点，子树中有y个点在联通块中，则答案为(x-y)*y。
代码：
1 var 2 i,n,m,cnt,cnt2,mm:longint; 3 j,k,l:int64; 4 b,fa:array[0..200001,1..2]of int64; 5 q:array[0..200001,0..2]of longint; 6 r,v,dep,c:array[0..200001]of longint; 7 xh:array[0..200001,1..2]of longint; 8 t:array[0..4000001,-2..2]of longint; 9 ch:char; 10 procedure ss(x,fa:longint); 11 var i:longint; 12 begin 13 v[x]:=1; i:=c[x]; inc(cnt); xh[x,1]:=cnt; dep[x]:=dep[fa]+1; 14 while i>0 do 15 begin 16 if b[i,1]<>fa then ss(b[i,1],x); 17 i:=b[i,2]; 18 end; 19 xh[x,2]:=cnt; 20 end; 21 function hb(x,y:longint):longint; 22 begin 23 if t[x,1]=t[x,2] then 24 begin t[x,0]:=t[x,0]+t[y,0]; exit(x); end; 25 if(t[x,-1]=0)and(t[y,-1]>0)then t[x,-1]:=t[y,-1] else 26 if(t[x,-1]>0)and(t[y,-1]>0)then t[x,-1]:=hb(t[x,-1],t[y,-1]); 27 if(t[x,-2]=0)and(t[y,-2]>0)then t[x,-2]:=t[y,-2] else 28 if(t[x,-2]>0)and(t[y,-2]>0)then t[x,-2]:=hb(t[x,-2],t[y,-2]); 29 t[x,0]:=t[t[x,-1],0]+t[t[x,-2],0]; 30 exit(x); 31 end; 32 function newt(l,r:longint):longint; 33 begin 34 inc(cnt2); t[cnt2,1]:=l; t[cnt2,2]:=r; exit(cnt2); 35 end; 36 procedure cl(x,y:longint); 37 var ll,rr:longint; 38 begin 39 ll:=t[x,1]; rr:=t[x,2]; inc(t[x,0]); 40 if ll=rr then exit; 41 if y<=(ll+rr)div 2 then 42 begin 43 if t[x,-1]=0 then t[x,-1]:=newt(ll,(ll+rr)div 2); 44 cl(t[x,-1],y); 45 end else 46 begin 47 if t[x,-2]=0 then t[x,-2]:=newt((ll+rr)div 2+1,rr); 48 cl(t[x,-2],y); 49 end; 50 end; 51 function qq(x,l,r:longint):longint; 52 var ll,rr:longint; 53 begin 54 if x=0 then exit(0); 55 ll:=t[x,1]; rr:=t[x,2]; 56 if(ll=l)and(rr=r)then exit(t[x,0]); 57 if r<=(ll+rr)div 2 then exit(qq(t[x,-1],l,r)); 58 if l>(ll+rr)div 2 then exit(qq(t[x,-2],l,r)); 59 exit(qq(t[x,-1],l,(ll+rr)div 2)+qq(t[x,-2],(ll+rr)div 2+1,r)); 60 end; 61 function get(x:longint):longint; 62 begin 63 if fa[x,1]<>x then fa[x,1]:=get(fa[x,1]); 64 exit(fa[x,1]); 65 end; 66 begin 67 readln(n,m); 68 for i:=1 to m do 69 begin 70 read(ch); readln(j,k); q[i,1]:=j; q[i,2]:=k; 71 if ch=‘A‘ then 72 begin 73 inc(mm); b[mm,1]:=k; b[mm,2]:=c[j]; c[j]:=mm; 74 inc(mm); b[mm,1]:=j; b[mm,2]:=c[k]; c[k]:=mm; 75 end else q[i,0]:=1; 76 end; 77 for i:=1 to n do 78 if v[i]=0 then ss(i,0); 79 for i:=1 to n do 80 begin 81 fa[i,1]:=i; fa[i,2]:=1; 82 r[i]:=newt(1,cnt); cl(r[i],xh[i,1]); 83 end; 84 for i:=1 to m do 85 begin 86 if q[i,0]=0 then 87 begin 88 j:=q[i,1]; k:=q[i,2]; 89 j:=get(j); k:=get(k); 90 fa[k,1]:=j; fa[j,2]:=fa[j,2]+fa[k,2]; 91 r[j]:=hb(r[j],r[k]); 92 end else 93 begin 94 j:=q[i,1]; k:=q[i,2]; 95 if dep[j]>dep[k] then begin l:=j; j:=k; k:=l; end; 96 j:=get(j); k:=qq(r[j],xh[k,1],xh[k,2]); 97 writeln(k*(fa[j,2]-k)); 98 end; 99 end; 100 end.
BZOJ4530[BJOI2014]大融合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。