神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。
输入数据的第一行是三个整数n,m,T。
第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这条边在start时刻出现，在第end时刻消失。
输出包含T行。在第i行中，如果第i时间段内这个图是二分图，那么输出“Yes”，否则输出“No”，不含引号。
3 3 3
1 2 0 2
2 3 0 3
1 3 1 2
Yes
No
Yes
样例说明：
0时刻，出现两条边1-2和2-3。
第1时间段内，这个图是二分图，输出Yes。
1时刻，出现一条边1-3。
第2时间段内，这个图不是二分图，输出No。
2时刻，1-2和1-3两条边消失。
第3时间段内，只有一条边2-3，这个图是二分图，输出Yes。
数据范围：
n<=100000，m<=200000，T<=100000，1<=u,v<=n，0<=start<=end<=T。
参照CQzhangyu的题解。
我们希望维护这样一个集合（本质是数组），保存的是当前时刻，所有加入之后会形成奇环的非树边。如果当前时刻集合中有元素，则不是一个二分图。那么删边的时候如何处理呢？如果我们删的是一条树边，那么假如集合中存在一条覆盖这条树边的非树边，那么这条非树边就会变成新的树边。这样的情况很难处理，所以我们希望保证：所有已经进入集合的非树边都不会从集合中出来再次成为树边，即，我们要维护的是关于删除时间的最大生成树。可以用LCT搞定。
凡是涉及断边操作又要用到边上信息的，都要把边拆成点来处理。这样的话判断奇环的时候，原来那条链上的点数是n，实际上加上边变成的点后的点数是2n-1，这样加上一条边后的点数是2n，要判断n是否是奇数，把它&2就行了。
时间复杂度\(O(m \log n)\)
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
typedef long long LL;
co int maxn=5e5+1;
int n,m,T,tot,sum;
int vis[maxn];
struct LCT{
int ch[2],fa,v,sm,rev,siz;
}s[maxn];
struct edge{
int pa,pb,t1,t2;
}p[maxn];
struct operate{
int tim,op,org;
bool operator<(co operate&o)co{
return tim==o.tim?op>o.op:tim<o.tim;
}
}q[maxn];
bool isr(int x){return s[s[x].fa].ch[0]!=x&&s[s[x].fa].ch[1]!=x;}
int MN(int a,int b){
return s[a].v<s[b].v?a:b;
}
void pushup(int x){
s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;
s[x].sm=MN(x,MN(s[s[x].ch[0]].sm,s[s[x].ch[1]].sm));
}
void pushdown(int x){
if(s[x].rev){
std::swap(s[x].ch[0],s[x].ch[1]);
if(s[x].ch[0]) s[s[x].ch[0]].rev^=1;
if(s[x].ch[1]) s[s[x].ch[1]].rev^=1;
s[x].rev=0;
}
}
void updata(int x){
if(!isr(x)) updata(s[x].fa);
pushdown(x);
}
void rotate(int x){
int y=s[x].fa,z=s[y].fa,d=x==s[y].ch[1];
if(!isr(y)) s[z].ch[y==s[z].ch[1]]=x;
s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];
if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;
s[x].ch[d^1]=y;
pushup(y),pushup(x);
}
void splay(int x){
updata(x);
while(!isr(x)){
int y=s[x].fa,z=s[y].fa;
if(!isr(y)) rotate(x==s[y].ch[1]^y==s[z].ch[1]?x:y);
rotate(x);
}
}
void access(int x){
for(int y=0;x;splay(x),s[x].ch[1]=y,pushup(x),x=s[y=x].fa);
}
void maker(int x){
access(x),splay(x),s[x].rev^=1;
}
void link(int x,int y){
access(x),splay(x),maker(y);
s[x].ch[1]=y,s[y].fa=x,pushup(x);
}
void cut(int x,int y){
maker(x),access(y),splay(y);
s[y].ch[0]=s[x].fa=0,pushup(y);
}
int findr(int x){
access(x),splay(x);
while(s[x].ch[0]) x=s[x].ch[0];
return x;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m),read(T);
for(int i=0;i<=n;++i) s[i].v=0x3f3f3f3f;
for(int i=1;i<=m;++i){
read(p[i].pa),read(p[i].pb),q[i].tim=read(p[i].t1),s[i+n].v=q[i+m].tim=read(p[i].t2);
s[i+n].siz=1,s[i+n].sm=i+n;
q[i].org=q[i+m].org=i,q[i].op=1,q[i+m].op=0;
}
std::sort(q+1,q+2*m+1);
for(int i=1,j=1;i<=T;++i){
for(;j<=2*m&&q[j].tim<i;++j){
int a=p[q[j].org].pa,b=p[q[j].org].pb,c=q[j].org+n;
if(q[j].op){
if(findr(a)!=findr(b)) link(a,c),link(b,c);
else{
maker(a),access(b),splay(b);
int d=s[b].sm;
if((s[b].siz+1)&2){
++sum;
if(s[d].v<s[c].v) cut(d,p[d-n].pa),cut(d,p[d-n].pb),link(a,c),link(b,c),vis[d]=1;
else vis[c]=1;
}
else{
if(s[d].v<s[c].v) cut(d,p[d-n].pa),cut(d,p[d-n].pb),link(a,c),link(b,c),vis[d]=2;
else vis[c]=2;
}
}
}
else{
if(!vis[c]) cut(c,a),cut(c,b);
if(vis[c]==1) --sum;
}
}
puts(sum?"No":"Yes");
}
return 0;
}原文：https://www.cnblogs.com/autoint/p/10416832.html