题目描述
神犇有一个 (n) 个节点的图。
因为神犇是神犇，所以在 (k) 时间内有 (m) 条边会出现后消失。
神犇要求出每一时间段内这个图是否是二分图。
这么简单的问题神犇当然会做了，于是他想考考你。
原 BZOJ4025。
输入格式
第一行三个整数 (n,m,k)。
接下来 (m) 行，每行四个整数 (x,y,l,r)，表示有一条连接 (x,y) 的边在 (l) 时刻出现 (r) 时刻消失。
输出格式
(k) 行，第 (i) 行一个字符串 Yes 或 No，表示在第 (i) 时间段内这个图是否是二分图。
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5,M=4e5+5;
inline int read(){
int x=0; char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x;
}
int fa[N],rnk[N];
struct FUCK{
int *x,y,*u,v;
};
stack<FUCK>st;
inline int get(int x){
while(x^fa[x])x=fa[x];
return x;
}
inline void merge(int x,int y){
x=get(x),y=get(y);
if(x==y)return;
if(rnk[x]>rnk[y])swap(x,y);
st.push((FUCK){fa+x,fa[x],rnk+y,rnk[y]});
fa[x]=y; rnk[y]+=(rnk[x]==rnk[y]);
}
inline void undo(){
*st.top().x=st.top().y;
*st.top().u=st.top().v;
st.pop();
}
#define mid ((l+r)>>1)
#define ls p<<1
#define rs p<<1|1
struct node{
int u,v;
};
vector<node>vec[M];
void update(int p,int l,int r,int L,int R,node d){
if(L<=l&&r<=R){ vec[p].push_back(d); return; }
if(L<=mid)update(ls,l,mid,L,R,d);
if(R>mid)update(rs,mid+1,r,L,R,d);
}
int n,m,k;
inline bool insert(int u,int v){
merge(u,v+n),merge(v,u+n);
return (get(u)==get(u+n)||get(v)==get(v+n));
}
void query(int p,int l,int r,bool op){
for(int i=0;i<vec[p].size();i++)op|=insert(vec[p][i].u,vec[p][i].v);
if(l==r){op?puts("No"):puts("Yes"); return;}
int sum=st.size();
query(ls,l,mid,op);
while(st.size()>sum)undo();
query(rs,mid+1,r,op);
}
signed main(){
n=read(),m=read(),k=read();
for(int i=1;i<=2*n;i++)fa[i]=i,rnk[i]=0;
for(int i=1,x,y,l,r;i<=m;i++){
x=read(),y=read(),l=read()+1,r=read();
update(1,1,k,l,r,(node){x,y});
}
query(1,1,k,0);
}