Steven_MengのBlog

传送门

本题暴力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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}$意义上面相等,把上面的式子带入,发现也是成立的,于是发现我们的式子很好地把两个条件都满足了


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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");
}

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

 评论