洛谷P5787 二分图 /【模板】线段树分治/BZOJ4025 二分图题解

2020-02-03 xiaoh

题意

给定一张有 $n$ 个节点的图( $1\leq n \leq 10^5$ )，初始情况下，图中没有任何边。接下来的 $k$ 秒中( $1\leq k \leq 10^5$ )，总共会出现 $m$ 条边( $1\leq m \leq 2×10^5$ )，第 $i$ 条边在第 $l_i$ 秒出现，第 $r_i$ 秒消失。求每一秒这张图是否是二分图。

题解

既然是模板题，那么当然要使用线段树二分啦。线段树二分的思路，简单来讲就是先将整个问题离线下来，以时间轴为坐标建立一颗线段树，然后对于每一个修改，就在线段树上对应的位置打上永久的标记。接下来以dfs遍历整棵树并在通过标记时将其计入答案。通常可以解决一些容易解决区间加法，却不易解决区间减法的问题。在本题中，我们只要用一个扩展域并查集维护原图是否是二分图即可。注意由于在递归到叶子后要回溯操作，因此不能使用路径压缩，因此考虑按秩合并，并记录下具体修改的点即可。（吐槽一下数据有多水，我按秩合并修改时忘记还原了，结果依然非常完美的卡了过去）时间复杂度O(mlogk+mlogklogn)。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010,MAXM=200010;
int n,m,k;
int tot=1;
int edge[MAXM*2],w[MAXM*2],nxt[MAXM*2],hd[MAXN];//前向星
inline void add_edge(int u,int v)
{
	edge[tot]=v,w[tot]=u,nxt[tot]=hd[u],hd[u]=tot++;
}
struct node{//线段树
	int l,r;//左右区间
	vector<int> f;//永久标记，表示该时间区间的添加的边
}f[MAXN*4];
void build(int p,int l,int r)//递归建树
{
	f[p].l=l,f[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p*2,l,mid),build(p*2+1,mid+1,r);
}
void modify(int p,int l,int r,int val)//区间修改，将边加入线段树中
{
	if(f[p].l>=l&&f[p].r<=r)
	{
		f[p].f.push_back(val);
		return;
	}
	int mid=(f[p].l+f[p].r)>>1;
	if(l<=mid) modify(p*2,l,r,val);
	if(r>mid) modify(p*2+1,l,r,val);
}
int a[MAXN*2],rk[MAXN*2];
inline void init()//初始化并查集
{
	for(int i=1;i<=2*n;i++) a[i]=i,rk[i]=1;
}
struct node2{//记录修改位置的结构体
	int a,b;
};
stack<node2> q;
int find(int x)//查询(不能使用路径压缩)
{
	return (x==a[x])? a[x]:find(a[x]);
}
int Union(int u,int v)//按秩合并
{
	u=find(u),v=find(v);
	if(find(u)==find(v)) return 0;
	if(rk[u]<=rk[v]) q.push({u,a[u]}),a[u]=v,rk[v]=max(rk[v],rk[u]+1);
	else q.push({v,a[v]}),a[v]=u,rk[u]=max(rk[u],rk[v]+1);
	return 1;
}
void back(int x)//注意此处写法有一些小问题，笔者忘记加上回溯秩rk的步骤了，但是依旧卡过了，请勿效仿
{
	for(int i=1;i<=x;i++) a[q.top().a]=q.top().b,q.pop();
}
void dfs(int p,bool ans)//递归整棵树求解答案
{
	int cnt=0;
	for(vector<int>::iterator it=f[p].f.begin();it!=f[p].f.end();it++)
	if(ans)
	{
		int x=edge[*it],y=w[*it];
		if(x==y)//若目前已经不是二分图了，那么所有的子节点也一定不是
		{
			ans=0;
			continue;
		}
		if(find(x)!=find(y)&&find(n+x)!=find(n+y)) cnt+=Union(x,n+y),cnt+=Union(y,n+x);
		else ans=0;
	}
	if(f[p].l==f[p].r)//递归边界
	{
		if(ans) printf("Yes\n");
		else printf("No\n");
		back(cnt);
		return;
	}
	dfs(p*2,ans),dfs(p*2+1,ans);
	back(cnt);
}
int main()
{
	read(n),read(m),read(k);
	build(1,1,k);
	for(int i=1;i<=m;i++)
	{
		int x,y,l,r;
		read(x),read(y),read(l),read(r);
		if(l>=r) continue;
		add_edge(x,y);
		modify(1,l+1,r,tot-1);
	}
	init();
	dfs(1,1);
	return 0;
}