首先我们要知道,怎么去维护一个是否是二分图
二分图的充要条件:点数>=2且无奇环
重点就是不存在奇环,怎么做呢
考虑随便维护一个图的生成树,不难发现,如果一条边加入后,形成奇环的话就不是二分图
否则的话,我们可以无视这条边,因为如果之后再新加入一条边和这条边形成了一个奇环
那么新加入的边一定和原来生成树上的边也能形成奇环
所以我们直接维护一棵生成树即可
然后裸的想法就来了:上lct,维护以离开时间为边权的最大生成树,每次加边弹出环上最早离开的边
然后还是那句话:cdq大法好
我们可以对时间线分治,考虑每条边对应时间段的影响
这样就只有加边而不用删边了,我们可以用并查集维护
然而应该怎么用并查集维护路径的奇偶性呢?方法是膜拜popoqqq的程序的,我简单说明一下
我们给每个点一个权值c,我们定义一个点i到并查集根的权值c的xor和(不包括根)为d[i]
定义两点间路径奇偶性为dis(x,y)=d[x] xor d[y]
当加入一条边x-y且x、y不连通时,假设p[x]是x所在并查集的根,并且我们现在把x所在集合并到y所在集合下
我们就令c[p[x]]=d[x] xor d[y] xor 1(d[]为加入这条边之前的值)
这个操作的保证了每个点权值最多被赋值一次
上述做法为什么能求出两点间路径长的奇偶性呢?我们来证明一下
首先是有边直接相连的两个点x,y,根据A xor B xor B=1的性质
可得dis(x,y)=d[x](加入边之前的) xor d[y] xor c[p[x]](加入边之前的)=d[x] xor d[x] xor d[y] xor d[y] xor 1=1
并且以后再加入别的边改变并查集后,dis(x,y)仍然为1(还是可以通过xor性质得知)
对于没有边直接连的两点x,y,我们只要证明dis(x,y)=dis(po[x],y) xor 1 即可(po[x]为x的一个邻居)
根据定义可得dis(x,y)=d[x] xor d[y] xor d[po[x]] xor d[po[x]]=dis(x,po[x]) xor dis(po[x],y)=1 xor dis(po[x],y)
所以通过上述方法,我们可以用并查集维护路径长的奇偶性
其他与bzoj3237的处理方法有些类似,并不需要可持久化,只需要栈来恢复即可
type node=record
x,y,s,t:longint;
end; var c,d,fa:array[..] of longint;
e:array[..] of node;
te:array[..*] of node;
st:array[..*] of longint;
ans:array[..] of boolean;
en,top,t,n,m,len,i,x,y,a,b:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function getf(x:longint):longint;
begin
while fa[x]<>x do x:=fa[x]; //路径压缩是均摊,所里这里不需要
exit(fa[x]);
end; function dis(x:longint):longint;
begin
dis:=;
while fa[x]<>x do
begin
dis:=dis xor c[x];
x:=fa[x];
end;
end; procedure union(x,y,w:longint);
begin
if d[x]>d[y] then swap(x,y); //按深度合并
fa[x]:=y;
inc(en);
st[en]:=x;
c[x]:=w;
if d[x]=d[y] then
begin
inc(en);
st[en]:=-y;
inc(d[y]);
end;
end; procedure rebuild(be:longint);
var x:longint;
begin
while be<>en do //两种情况的恢复
begin
x:=st[en];
if x< then
dec(d[-x])
else begin
fa[x]:=x;
c[x]:=;
end;
dec(en);
end;
end; procedure add(x,y,a,b:longint);
begin
inc(len);
e[len].x:=x;
e[len].y:=y;
e[len].s:=a;
e[len].t:=b;
end; procedure cdq(m,l,r:longint);
var mid,x,y,w,be,j,dow:longint;
begin
be:=en;
mid:=(l+r) shr ;
for i:= to m do
if (e[i].s=l) and (e[i].t=r) then
begin
x:=getf(e[i].x);
y:=getf(e[i].y);
w:=dis(e[i].x) xor dis(e[i].y) xor ;
if x<>y then union(x,y,w)
else if w= then
begin
for j:=l to r do
ans[j]:=false;
rebuild(be);
exit;
end;
end;
if l=r then ans[l]:=true
else begin
len:=;
dow:=top;
for i:= to m do //划分边集
begin
if (e[i].s=l) and (e[i].t=r) then continue;
inc(top);
te[top]:=e[i];
if e[i].t<=mid then
begin
inc(len);
e[len]:=e[i];
end
else if e[i].s<=mid then
add(e[i].x,e[i].y,e[i].s,mid);
end;
cdq(len,l,mid);
len:=;
for i:=top downto dow+ do
if te[i].s>mid then
begin
inc(len);
e[len]:=te[i];
end
else if te[i].t>mid then
add(te[i].x,te[i].y,mid+,te[i].t);
top:=dow;
cdq(len,mid+,r);
end;
rebuild(be);
end; begin
readln(n,m,t);
for i:= to m do
begin
readln(x,y,a,b);
inc(a);
if a>b then continue;
add(x,y,a,b);
end;
for i:= to n do
begin
fa[i]:=i;
d[i]:=;
end;
cdq(m,,t);
for i:= to t do
if ans[i] then writeln('Yes') else writeln('No');
end.