【BZOJ4736】温暖会指引我们前行（LCT）

题意：有一张图，每条边有一个不同的编号，长度和权值，维护以下操作：

1.加边

2.修改边长

3.询问两点之间在最小权值最大的前提下的唯一路径长度

n<=100000 m<=300000

思路：RYZ作业

BZOJ上有四组数据的输入不完整，输出没问题

LCT维护最大生成树，维护子树和，和子树中权值最小的位置即可

  1 var t:array[0..700000,0..1]of longint;
  2     sum:array[0..700000]of int64;
  3     f:array[1..700000,1..2]of longint;
  4     w,l1,mx,fa,q,rev:array[0..700000]of longint;
  5     n,m,x,y,top,tot,id,i,len,s,ll,tt,j,tmp,now:longint;
  6     ch:string;
  7 
  8 procedure swap(var x,y:longint);
  9 var t:longint;
 10 begin
 11  t:=x; x:=y; y:=t;
 12 end;
 13 
 14 function isroot(x:longint):boolean;
 15 begin
 16  if (t[fa[x],0]<>x)and(t[fa[x],1]<>x) then exit(true);
 17  exit(false);
 18 end;
 19 
 20 procedure pushup(x:longint);
 21 var l,r:longint;
 22 begin
 23  l:=t[x,0]; r:=t[x,1];
 24  sum[x]:=sum[l]+sum[r]+l1[x];
 25  mx[x]:=x;
 26  if w[mx[l]]<w[mx[x]] then mx[x]:=mx[l];
 27  if w[mx[r]]<w[mx[x]] then mx[x]:=mx[r];
 28 end;
 29 
 30 procedure pushdown(x:longint);
 31 var l,r:longint;
 32 begin
 33  l:=t[x,0]; r:=t[x,1];
 34  if rev[x]>0 then
 35  begin
 36   rev[x]:=rev[x] xor 1; rev[l]:=rev[l] xor 1; rev[r]:=rev[r] xor 1;
 37   swap(t[x,0],t[x,1]);
 38  end;
 39 end;
 40 
 41 procedure rotate(x:longint);
 42 var y,z,l,r:longint;
 43 begin
 44  y:=fa[x]; z:=fa[y];
 45  if t[y,0]=x then l:=0
 46   else l:=1;
 47  r:=l xor 1;
 48  if not isroot(y) then
 49  begin
 50   if t[z,0]=y then t[z,0]:=x
 51    else t[z,1]:=x;
 52  end;
 53  fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;
 54  t[y,l]:=t[x,r]; t[x,r]:=y;
 55  pushup(y);
 56  pushup(x);
 57 end;
 58 
 59 procedure splay(x:longint);
 60 var k,y,z:longint;
 61 begin
 62  inc(top); q[top]:=x;
 63  k:=x;
 64  while not isroot(k) do
 65  begin
 66   inc(top); q[top]:=fa[k];
 67   k:=fa[k];
 68  end;
 69  while top>0 do
 70  begin
 71   pushdown(q[top]);
 72   dec(top);
 73  end;
 74 
 75  while not isroot(x) do
 76  begin
 77   y:=fa[x]; z:=fa[x];
 78   if not isroot(y) then
 79   begin
 80    if (t[y,0]=x)xor(t[z,0]=y) then rotate(x)
 81     else rotate(y);
 82   end;
 83   rotate(x);
 84  end;
 85 end;
 86 
 87 procedure access(x:longint);
 88 var last:longint;
 89 begin
 90  last:=0;
 91  while x>0 do
 92  begin
 93   splay(x); t[x,1]:=last; pushup(x);
 94   last:=x; x:=fa[x];
 95  end;
 96 end;
 97 
 98 procedure makeroot(x:longint);
 99 begin
100  access(x); splay(x); rev[x]:=rev[x] xor 1;
101 end;
102 
103 procedure link(x,y:longint);
104 begin
105  makeroot(x); fa[x]:=y;
106 end;
107 
108 procedure split(x,y:longint);
109 begin
110  makeroot(x); access(y); splay(y);
111 end;
112 
113 procedure cut(x,y:longint);
114 begin
115  makeroot(x); access(y); splay(y); t[y,0]:=0; fa[x]:=0;
116 end;
117 
118 function findroot(x:longint):longint;
119 var k:longint;
120 begin
121  access(x); splay(x);
122  k:=x;
123  while t[k,0]<>0 do k:=t[k,0];
124  exit(k);
125 end;
126 
127 begin
128  assign(input,'bzoj4736.in'); reset(input);
129  assign(output,'bzoj4736.out'); rewrite(output);
130  readln(n,m);
131  fillchar(w,sizeof(w),$7f);
132  //fillchar(l,sizeof(l),$1f);
133  for i:=1 to m do
134  begin
135   readln(ch); s:=0; id:=0; x:=0; y:=0; tt:=0; ll:=0;
136   len:=length(ch);
137   case ch[1] of
138    'f':
139    begin
140     for j:=5 to len do
141     begin
142      if ch[j]=' ' then begin inc(s); continue; end;
143      tmp:=ord(ch[j])-ord('0');
144      case s of
145       1:id:=id*10+tmp;
146       2:x:=x*10+tmp;
147       3:y:=y*10+tmp;
148       4:tt:=tt*10+tmp;
149       5:ll:=ll*10+tmp;
150      end;
151     end;
152     inc(x); inc(y); inc(id);
153     tot:=id+150000;
154     w[tot]:=tt; l1[tot]:=ll; f[tot,1]:=x; f[tot,2]:=y;
155     if findroot(x)<>findroot(y) then
156     begin
157      mx[tot]:=tot;
158      link(x,tot); link(tot,y);
159     end
160      else
161      begin
162       split(x,y);
163       now:=mx[y];
164       if w[now]<tt then
165       begin
166        cut(f[now,1],now); cut(now,f[now,2]);
167        mx[tot]:=tot;
168        link(x,tot); link(tot,y);
169       end;
170      end;
171 
172    end;
173    'm':
174    begin
175     for j:=5 to len do
176     begin
177      if ch[j]=' ' then begin inc(s); continue; end;
178      tmp:=ord(ch[j])-ord('0');
179      case s of
180       1:x:=x*10+tmp;
181       2:y:=y*10+tmp;
182      end;
183     end;
184     inc(x); inc(y);
185     if findroot(x)<>findroot(y) then writeln(-1)
186      else
187      begin
188       split(x,y); writeln(sum[y]);
189      end;
190     end;
191    'c':
192    begin
193     for j:=7 to len do
194     begin
195      if ch[j]=' ' then begin inc(s); continue; end;
196      tmp:=ord(ch[j])-ord('0');
197      case s of
198       1:id:=id*10+tmp;
199       2:ll:=ll*10+tmp;
200      end;
201     end;
202     inc(id); tot:=id+150000;
203     splay(tot);
204     l1[tot]:=ll;
205     pushup(tot);
206    end;
207   end;
208  end;
209  close(input);
210  close(output);
211 end.

2017.3.9

突然发现前一个代码splay打错了一个字母导致退化成类似单旋的东西

神TM单旋也能过

  1 var t:array[0..2000000,0..1]of longint;
  2     sum:array[0..2000000]of int64;
  3     f:array[1..2000000,1..2]of longint;
  4     w,l1,mx,fa,q,rev:array[0..2000000]of longint;
  5     n,m,x,y,top,tot,id,i,len,s,ll,tt,j,tmp,now:longint;
  6     ch:string;
  7 
  8 procedure swap(var x,y:longint);
  9 var t:longint;
 10 begin
 11  t:=x; x:=y; y:=t;
 12 end;
 13 
 14 function isroot(x:longint):boolean;
 15 begin
 16  if (t[fa[x],0]<>x)and(t[fa[x],1]<>x) then exit(true);
 17  exit(false);
 18 end;
 19 
 20 procedure pushup(x:longint);
 21 var l,r:longint;
 22 begin
 23  l:=t[x,0]; r:=t[x,1];
 24  sum[x]:=sum[l]+sum[r]+l1[x];
 25  mx[x]:=x;
 26  if w[mx[l]]<w[mx[x]] then mx[x]:=mx[l];
 27  if w[mx[r]]<w[mx[x]] then mx[x]:=mx[r];
 28 end;
 29 
 30 procedure pushdown(x:longint);
 31 var l,r:longint;
 32 begin
 33  l:=t[x,0]; r:=t[x,1];
 34  if rev[x]>0 then
 35  begin
 36   rev[x]:=rev[x] xor 1; rev[l]:=rev[l] xor 1; rev[r]:=rev[r] xor 1;
 37   swap(t[x,0],t[x,1]);
 38  end;
 39 end;
 40 
 41 procedure rotate(x:longint);
 42 var y,z,l,r:longint;
 43 begin
 44  y:=fa[x]; z:=fa[y];
 45  if t[y,0]=x then l:=0
 46   else l:=1;
 47  r:=l xor 1;
 48  if not isroot(y) then
 49  begin
 50   if t[z,0]=y then t[z,0]:=x
 51    else t[z,1]:=x;
 52  end;
 53  fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;
 54  t[y,l]:=t[x,r]; t[x,r]:=y;
 55  pushup(y);
 56  pushup(x);
 57 end;
 58 
 59 procedure splay(x:longint);
 60 var k,y,z:longint;
 61 begin
 62  inc(top); q[top]:=x;
 63  k:=x;
 64  while not isroot(k) do
 65  begin
 66   inc(top); q[top]:=fa[k];
 67   k:=fa[k];
 68  end;
 69  while top>0 do
 70  begin
 71   pushdown(q[top]);
 72   dec(top);
 73  end;
 74 
 75  while not isroot(x) do
 76  begin
 77   y:=fa[x]; z:=fa[y];
 78   if not isroot(y) then
 79   begin
 80    if (t[y,0]=x)xor(t[z,0]=y) then rotate(x)
 81     else rotate(y);
 82   end;
 83   rotate(x);
 84  end;
 85 end;
 86 
 87 procedure access(x:longint);
 88 var last:longint;
 89 begin
 90  last:=0;
 91  while x>0 do
 92  begin
 93   splay(x); t[x,1]:=last; pushup(x);
 94   last:=x; x:=fa[x];
 95  end;
 96 end;
 97 
 98 procedure makeroot(x:longint);
 99 begin
100  access(x); splay(x); rev[x]:=rev[x] xor 1;
101 end;
102 
103 procedure link(x,y:longint);
104 begin
105  makeroot(x); fa[x]:=y;
106 end;
107 
108 procedure split(x,y:longint);
109 begin
110  makeroot(x); access(y); splay(y);
111 end;
112 
113 procedure cut(x,y:longint);
114 begin
115  makeroot(x); access(y); splay(y); t[y,0]:=0; fa[x]:=0;
116 end;
117 
118 function findroot(x:longint):longint;
119 var k:longint;
120 begin
121  access(x); splay(x);
122  k:=x;
123  while t[k,0]<>0 do k:=t[k,0];
124  exit(k);
125 end;
126 
127 begin
128  assign(input,'bzoj4736.in'); reset(input);
129  assign(output,'bzoj4736.out'); rewrite(output);
130  readln(n,m);
131  fillchar(w,sizeof(w),$7f);
132  //fillchar(l,sizeof(l),$1f);
133  for i:=1 to m do
134  begin
135   readln(ch); s:=0; id:=0; x:=0; y:=0; tt:=0; ll:=0;
136   len:=length(ch);
137   case ch[1] of
138    'f':
139    begin
140     for j:=5 to len do
141     begin
142      if ch[j]=' ' then begin inc(s); continue; end;
143      tmp:=ord(ch[j])-ord('0');
144      case s of
145       1:id:=id*10+tmp;
146       2:x:=x*10+tmp;
147       3:y:=y*10+tmp;
148       4:tt:=tt*10+tmp;
149       5:ll:=ll*10+tmp;
150      end;
151     end;
152     inc(x); inc(y); inc(id);
153     tot:=id+150000;
154     w[tot]:=tt; l1[tot]:=ll; f[tot,1]:=x; f[tot,2]:=y;
155     if findroot(x)<>findroot(y) then
156     begin
157      mx[tot]:=tot;
158      link(x,tot); link(tot,y);
159     end
160      else
161      begin
162       split(x,y);
163       now:=mx[y];
164       if w[now]<tt then
165       begin
166        cut(f[now,1],now); cut(now,f[now,2]);
167        mx[tot]:=tot;
168        link(x,tot); link(tot,y);
169       end;
170      end;
171 
172    end;
173    'm':
174    begin
175     for j:=5 to len do
176     begin
177      if ch[j]=' ' then begin inc(s); continue; end;
178      tmp:=ord(ch[j])-ord('0');
179      case s of
180       1:x:=x*10+tmp;
181       2:y:=y*10+tmp;
182      end;
183     end;
184     inc(x); inc(y);
185     if findroot(x)<>findroot(y) then writeln(-1)
186      else
187      begin
188       split(x,y); writeln(sum[y]);
189      end;
190     end;
191    'c':
192    begin
193     for j:=7 to len do
194     begin
195      if ch[j]=' ' then begin inc(s); continue; end;
196      tmp:=ord(ch[j])-ord('0');
197      case s of
198       1:id:=id*10+tmp;
199       2:ll:=ll*10+tmp;
200      end;
201     end;
202     inc(id); tot:=id+150000;
203     splay(tot);
204     l1[tot]:=ll;
205     pushup(tot);
206    end;
207   end;
208  end;
209  close(input);
210  close(output);
211 end.