天天看点

【BZOJ 4025】二分图

传送门

problem

出一个 n n n 个节点的图,有 m m m 条边,每条边会在 s i s_i si​ 时刻出现,在 t i t_i ti​ 消失。对于 ∀ i ∈ [ 1 , T ] \forall i\in[1,T] ∀i∈[1,T],请查询在 i i i 时刻图是否为二分图。

数据范围: n , T ≤ 1 0 5 n,T\le10^5 n,T≤105, m ≤ 2 × 1 0 5 m\le2\times 10^5 m≤2×105, 0 ≤ s i ≤ t i ≤ T 0\le s_i\le t_i\le T 0≤si​≤ti​≤T。

solution

这是一道线段树分治的板子题。

首先有一个结论,即一个图是二分图的充要条件是不含奇环。

因为有删边操作,我们用线段树分治,现在的任务就是如何判奇环。

加边时,若 ( u , v ) (u,v) (u,v) 不连通,那么不会构成环,把它加进来。

若 ( u , v ) (u,v) (u,v) 已经联通,则查询 u u u 和 v v v 两点的距离。若为偶数则加上这条边后会形成奇环,那么图之后都不可能是二分图,直接判掉即可。若为奇数则可以直接忽略这条边,因为如果将来某条边会与这条边形成奇环,则用之前 u u u 到 v v v 之间的路径(长度为奇数)替代这条边(长度为 1 1 1)同样也会形成奇环。

由于我们只需要维护奇偶性,可以直接用异或操作。

时间复杂度 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n)。

code

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
typedef pair<int,int> Pair;
int n,m,T;
int fa[N],ans[N],Rank[N],val[N];
struct node{
	Pair del;bool flag;
	node(Pair _del,bool _flag):del(_del),flag(_flag){}
};
vector<Pair>e[N<<2];
vector<node>op[N<<2];
void Modify(int root,int l,int r,int x,int y,int u,int v){
	if(l>=x&&r<=y){
		return e[root].push_back(make_pair(u,v));
	}
	int mid=(l+r)>>1;
	if(x<=mid)  Modify(root<<1,l,mid,x,y,u,v);
	if(y>mid)  Modify(root<<1|1,mid+1,r,x,y,u,v);
}
int find(int &x){
	int now=0;
	while(x!=fa[x])  now^=val[x],x=fa[x];
	return now;
}
void Query(int root,int l,int r){
	bool flag=true,now;
	for(int i=0;i<e[root].size();++i){
		int x=e[root][i].first,y=e[root][i].second,u=find(x),v=find(y);
		if(x==y){
			if(!(u^v)){
				flag=false;
				for(int i=l;i<=r;++i)  ans[i]=0;
				break;
			}
			continue;
		}
		if(Rank[x]<Rank[y])  swap(x,y);
		fa[y]=x,val[y]=u^v^1,now=0;
		if(Rank[x]==Rank[y])  ++Rank[x],now=1;
		op[root].push_back(node(make_pair(x,y),now));
	}
	int mid=(l+r)>>1;
	if(l!=r&&flag)  Query(root<<1,l,mid),Query(root<<1|1,mid+1,r);
	for(int i=op[root].size()-1;~i;--i){
		int x=op[root][i].del.first,y=op[root][i].del.second;
		fa[y]=y,val[y]=0,Rank[x]-=op[root][i].flag;
	}
}
int main(){
	int u,v,l,r;
	scanf("%d%d%d",&n,&m,&T);
	for(int i=1;i<=n;++i)  fa[i]=i,ans[i]=Rank[i]=1;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&l,&r);
		if(l<r)  Modify(1,1,T,l+1,r,u,v);
	}
	Query(1,1,T);
	for(int i=1;i<=T;++i)  puts(ans[i]?"Yes":"No");
	return 0;
}