Steven_Meng's Blog

传送门

本题暴力：

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	} 
	return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
	G[u].push_back(v);
}
int col[MAXN],vis[MAXN];
inline void Init(){
	memset(col,0,sizeof(col)),memset(vis,0,sizeof(vis));
	for (register int i=0;i<MAXN;++i) G[i].clear();
}
vector<int>E[MAXN];
int U[MAXN],V[MAXN];
inline bool Check(int u){
	vis[u]=true;
	for (register int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if (vis[v]&&col[v]!=(!col[u])) return false;
		else if (!vis[v]){
			col[v]=!col[u];
			Check(v);
		} 
	}
	return true;
}
inline void AddE(int j){
	for (register int i=0;i<E[j].size();++i){
		int id=E[j][i];
		AddEdge(U[id],V[id]);
		AddEdge(V[id],U[id]);
	}
}
int main(){
	int n=read(),m=read(),T=read();
	for (register int i=1;i<=m;++i) {
		U[i]=read(),V[i]=read();
		int s=read(),e=read();
		for (register int j=s;j<e;++j) E[j].push_back(i);
	}
	for (register int i=0;i<T;++i){
		Init();
		AddE(i);
		bool flag=true;
		for (register int j=1;j<=n;++j){
			if (!vis[j]){
				if (!Check(j)) {
					flag=false;
					break;
				}
			}
		}
		puts(flag?"Yes":"No");
	}
	return 0;
}

注意到暴力的时候，我们从$t$转移到$t+1$的时候，可能只会加入少量的边，如果每次$O(n)$计算，会造成大量重复计算。

注意到这张图是二分图等价于这张图里面没有奇环，于是可以并查集维护，维护每个点到它的父亲节点的距离，注意要支持可撤销，所以需要启发式合并。

不妨换一个思路，对于一个时刻$t$，只有$t \in [s,e]$，$[s,e]$区间里面的加边操作才能对答案产生影响，这个结论可以推广，对于时间在$[l,r]$的答案（不妨在这段答案全部都是$\rm Yes$或者$\rm No$），只有$[l,r] \in [s,e]$，$[s,e]$区间里面的操作才会对答案产生影响，于是我们想要查询$[l,r]$的答案时，先要把$[l,r] \in [s,e]$的操作全部做完，如果操作做完之后，产生奇环，那么就把这段区间的答案全部设成$\rm No$，并且撤销并查集。

这样说得有点玄学，为甚假定答案都是一样的呢，看不懂没有关系，请继续往下：

考虑一个类似于线段树的分治结构，$Solve(l,r,E)$表示总的边集为$E$，求解$[l,r]$区间的答案，如果按照上面所说地加边，出现奇环，那么将$[l,r]$的答案设成$\rm No$，撤销并查集，退出递归，因为之后不管怎么加边，都不可能将这个图变回二分图，如果没有出现奇环，找出来所有$s \le mid$的边，加入左边的集合$L$，$e > mid$的边加入右边的集合$R$，递归求解$Solve(l,mid,L),Solve(mid+1,r,R)$。

看到这里你应该明白了，其实这个递归过程是把答案序列按照线段树建树的模式分成许多段，每段答案都是$\rm No$，

如图所示，标成红色代表这段答案都是$\rm No$，停止递归，标成灰色代表这段根本递归不到，标成绿色代表确定了答案是$\rm Yes$（绿色只在叶子节点有），标成蓝色代表不知道这段答案是$\rm Yes$还是$\rm No$。

这样为什么是正确的呢，因为对于所有$s\le l,e \geq r$，都被算在并查集里面，递归求解$Solve(l,mid,L)$的时候，发现只要考虑$s \le l,e \in [mid+1,r)$的边，（其他的情况就是$s \le l ,e \geq r$，在上面的递归里面算到了），刚好是我们加进$L$的边，但是注意到我们加进$L$的不是$e > mid$的边，为什么呢，发现我们还要照顾到$s \le mid$的边，虽然这些边不一定在下一次递归会加入并查集，但是在更深层的递归就可能，不能把他们漏掉。

时间复杂度分析：注意到每条边至多算一次，于是时间复杂度$O(n \log ^2 n)$（启发式合并还有一个$\log $）

这样使用线段树，巧妙地减少了加边的次数。

接下来考虑并查集如何实现

注意到我们要使$\forall w \in subtree(fa(u))$，$v -> fa(v) -> fa(u) -> w$和$v -> u -> w$长度在$\mod 2$意义上面是相等的。

于是$dep(v)+val[fa(v)]+dep(w)\equiv 1+dep(u)+dep(w)-dep(LCA(u,w)) \times 2 \pmod{2}$

化一下：$val[fa(v)]\equiv dep(u)-dep(v)+1 \pmod{2}$

这个式子等价于$val[fa(v)]\equiv dep(u)+dep(v)+1 \pmod{2}$

注意到我们还有一个条件要满足：

$\forall w \in subtree(fa(v))$，$u -> fa(u) -> fa(v) -> w$和$u -> v -> w$长度在$\mod{2}$意义上面相等，把上面的式子带入，发现也是成立的，于是发现我们的式子很好地把两个条件都满足了

代码实现：

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
    #define P pair<int,int>
    #define mp make_pair
    int fa[MAXN],sz[MAXN],val[MAXN];
    inline void Init(int n){
        for (register int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
    }
    int GetDep(int i){
        return fa[i]==i?val[i]:GetDep(fa[i])+val[i];
    }
    int Find(int i){
        return fa[i]==i?i:Find(fa[i]);
    }
    inline bool Merge(int u,int v,stack<P> &s){//形成奇环return false，else return true
        int tu=u,tv=v;
        u=Find(u),v=Find(v);
        if (u==v){
            return !((GetDep(tu)+GetDep(tv))%2==0);
        }
        if (sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v],fa[v]=u;
        val[v]=GetDep(tu)+GetDep(tv)+1;
        s.push(mp(u,v));
        return true;
    }
    inline void Reverse(stack<P> &s){//回溯
        while (s.size()){
            int u=s.top().first,v=s.top().second;
            fa[v]=v,sz[u]-=sz[v],val[v]=0;
            s.pop();
        }
    }
}
using namespace BCJ;
struct Edge{
    int u,v,l,r;
};
int Ans[MAXN];
void Solve(int l,int r,vector<Edge> &A){
    vector<Edge>L,R;
    stack<P>s;//用来撤销的栈
    bool flag=true;
    int mid=(l+r)>>1;
    for (register int i=0;i<A.size();++i){
        if (A[i].l<=l&&r<=A[i].r){//只要记录跨越左右的边
            if (!Merge(A[i].u,A[i].v,s)){
                for (register int i=l;i<=r;++i) Ans[i]=0;//这样不用递归下去，因为都是0
                flag=false;
                break;
            }
        }
        else {
            if (A[i].l<=mid) L.push_back(A[i]);
            if (A[i].r>mid) R.push_back(A[i]);
        }
    }
    if (flag&&l<r){Solve(l,mid,L);Solve(mid+1,r,R);}
    Reverse(s);//回溯
}
int main(){
    int n=read(),m=read(),T=read();
    vector<Edge>A;
    for (register int i=1;i<=m;++i){
        int u=read(),v=read(),l=read(),r=read();
        A.push_back(Edge{u,v,l+1,r});
    }
    Init(n);
    for (register int i=1;i<=T;++i) Ans[i]=true;
    Solve(1,T,A);
    for (register int i=1;i<=T;++i) puts(Ans[i]?"Yes":"No");
}

总结：这类和时间/区间有关的题目大多数要用到线段树分治。