[BZOJ 4025]二分图(线段树分治+带边权并查集)

题面

给出一个n个点m条边的图，每条边会在时间s到t出现，问每个时间的图是否为一个二分图

\(n,m,\max(t_i) \leq 10^5\)

分析

我们知道一个图是二分图的充要条件是图中不存在奇环。于是可以用边带权并查集维护两点间距离的奇偶性，每次加边的时候，如果新加入的边会产生一个偶环，那加不加这条边都不影响结果，直接跳过；如果加入的边会产生奇环，那么就更新答案。

考虑如何删除一条边。如果我们不路径压缩而是用按秩合并的话，那么可以通过一个栈撤销对fa数组的修改。但是每次删除都这样做是\(O(n^2)\)的，考虑优化。

看到时间，我们就想到了离线分治算法。我们按时间分治。我们每次递归计算时间为[l,r]时的答案。我们将满足存在时间\([l,r] \in[s,t]\)的边加入，那么加入的边在\([l,r]\)时间内一定是一直存在的。如果加入这些边的时候出现了奇环，那么时间\([l,r]\)内的图一定不可能是二分图，直接更新\([l,r]\)的答案然后返回。如果没有出现奇环，就递归处理[l,mid],[mid+1,r]。直到出现奇环了再回溯。回溯的时候用栈撤销处理这一个区间的时并查集上的修改操作。

由于这个递归过程类似线段树，所以叫线段树分治。对于每个区间，算上并查集的复杂度，时间复杂度为\(O((r-l+1)\log n)\).显然最多递归\(O(\log n)\)层,每层所有的区间加起来长度为\(n\),总时间复杂度\(O(n \log ^2n)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define maxn 100000

using namespace std;

int n,m,T;

int ans[maxn+5];

struct disjoint_set{

	int fa[maxn+5];

	int deep[maxn+5];

	int sz[maxn+5];

	void ini(int n){

		for(int i=1;i<=n;i++){

			fa[i]=0;

			sz[i]=1;

		}

	}

	int find(int x){

		while(fa[x]!=0) x=fa[x];

		return x;

	}

	int get_deep(int x){

		int ans=0;

		while(fa[x]!=0){

			ans^=deep[x];

			x=fa[x];

		}

		ans^=deep[x];

		return ans;

	}

	int top=0;

	bool check(int x,int y){

		int fx=find(x),fy=find(y);

		int dx=get_deep(x),dy=get_deep(y);

		if(fx==fy){

			if((dx^dy^1)==1) return 1;

			else return 0;

		}else return 0;

	}

	void merge(int x,int y,vector< pair<int,int> > &stk){

		int fx=find(x),fy=find(y);

		int dx=get_deep(x),dy=get_deep(y);

		if(fx!=fy){

			if(sz[fx]>sz[fy]) swap(fx,fy);

			fa[fx]=fy;

			deep[fx]=dx^dy^1;

			sz[fy]+=sz[fx];

			stk.push_back(make_pair(fx,fy));//准备撤销操作

		}

	}

	void del(int fx,int fy){//撤销

		fa[fx]=0;

		deep[fx]=0;

		sz[fy]-=sz[fx];

	}

}S;

vector< pair<int,int> >E[maxn*4+5];//能够覆盖区间[l,r]的边

vector< pair<int,int> > stk[maxn*4+5];//分治到每个区间回滚用的栈

void update(int L,int R,pair<int,int> val,int l,int r,int pos){

	if(L<=l&&R>=r){

		E[pos].push_back(val);

		return;

	}

	int mid=(l+r)>>1;

	if(L<=mid) update(L,R,val,l,mid,pos<<1);

	if(R>mid) update(L,R,val,mid+1,r,pos<<1|1);

}

void divide(int l,int r,int pos){

	bool flag=0;

	for(int i=0;i<(int)E[pos].size();i++){

		int x=E[pos][i].first;

		int y=E[pos][i].second;

		if(S.check(x,y)){//存在奇环

			flag=1;

			for(int i=l;i<=r;i++) ans[i]=0;

			break;

		}

		S.merge(x,y,stk[pos]);

	}

	int mid=(l+r)>>1;

	if(l!=r&&!flag){//没有奇环，继续递归

		divide(l,mid,pos<<1);

		divide(mid+1,r,pos<<1|1);

	}

	for(int i=(int)stk[pos].size()-1;i>=0;i--){//回滚

		S.del(stk[pos][i].first,stk[pos][i].second);

	}

}

int main(){

	int u,v,l,r;

	scanf("%d %d %d",&n,&m,&T);

	S.ini(n);

	for(int i=1;i<=T;i++) ans[i]=1;

	for(int i=1;i<=m;i++){

		scanf("%d %d %d %d",&u,&v,&l,&r);

		l++;

		update(l,r,make_pair(u,v),1,T,1);

	}

	divide(1,T,1);

	for(int i=1;i<=T;i++){

		if(ans[i]) puts("Yes");

		else puts("No");

	}

}