BZOJ4025 二分图 分治+并查集

2018-01-05jzqjzq?

文章目录

原题链接:BZOJ4025
原来想LCT的,发现忘记LCT怎么打了,然后看了下Po姐的题解,发现原来还有这么好的做法
考虑分治,每次到一个区间枚举所有边,如果这个区间被包含,我们把它加进并查集,判断是否有奇环
如果没有被包含,我们分治到下一层进行处理。
差不多就是这么做的啦

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
struct ppap{int x,y,l,r;};
int n,m,T;
vector<ppap>e;
int fa[100010],d[100010],s[200010],rk[100010];
inline int find(int x){return fa[x]==x?x:find(fa[x]);}
inline int dis(int x){return fa[x]==x?0:d[x]^dis(fa[x]);}
inline void hb(int x,int y,int z){
int fx=find(x),fy=find(y);
if(fx==fy)return;
if(rk[fx]>rk[fy])swap(fx,fy);
if(rk[fx]==rk[fy])rk[fy]++,s[++s[0]]=-fy;
fa[fx]=fy;d[fx]=z;s[++s[0]]=fx;
}
inline void hy(int x){
while(s[0]>x){
if(s[s[0]]<0)rk[-s[s[0]--]]--;
else fa[s[s[0]]]=s[s[0]],d[s[s[0]--]]=0;
}
}
inline void work(int l,int r,vector<ppap> &e){
int mid=l+r>>1,L=e.size(),K=s[0];
vector<ppap>el,er;
for(int i=0;i<L;i++){
ppap now=e[i];
if(now.l==l&&now.r==r){
int x=find(now.x),y=find(now.y);
int z=dis(now.x)^dis(now.y)^1;
if(x!=y)hb(x,y,z);
else if(z){
for(int i=l;i<=r;i++)puts("No");
hy(K);return;
}
}else if(now.r<=mid)el.push_back(now);
else if(now.l>mid)er.push_back(now);
else{
el.push_back((ppap){now.x,now.y,now.l,mid});
er.push_back((ppap){now.x,now.y,mid+1,now.r});
}
}
if(l==r)puts("Yes");
else work(l,mid,el),work(mid+1,r,er);
hy(K);
}
int main()
{
n=read();m=read();T=read();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int x=read(),y=read(),l=read(),r=read();
if(l==r)continue;
e.push_back((ppap){x,y,l+1,r});
}
work(1,T,e);
return 0;
}