传送门
problem
出一个 n n n 个节点的图,有 m m m 条边,每条边会在 s i s_i si 时刻出现,在 t i t_i ti 消失。对于 ∀ i ∈ [ 1 , T ] \forall i\in[1,T] ∀i∈[1,T],请查询在 i i i 时刻图是否为二分图。
数据范围: n , T ≤ 1 0 5 n,T\le10^5 n,T≤105, m ≤ 2 × 1 0 5 m\le2\times 10^5 m≤2×105, 0 ≤ s i ≤ t i ≤ T 0\le s_i\le t_i\le T 0≤si≤ti≤T。
solution
这是一道线段树分治的板子题。
首先有一个结论,即一个图是二分图的充要条件是不含奇环。
因为有删边操作,我们用线段树分治,现在的任务就是如何判奇环。
加边时,若 ( u , v ) (u,v) (u,v) 不连通,那么不会构成环,把它加进来。
若 ( u , v ) (u,v) (u,v) 已经联通,则查询 u u u 和 v v v 两点的距离。若为偶数则加上这条边后会形成奇环,那么图之后都不可能是二分图,直接判掉即可。若为奇数则可以直接忽略这条边,因为如果将来某条边会与这条边形成奇环,则用之前 u u u 到 v v v 之间的路径(长度为奇数)替代这条边(长度为 1 1 1)同样也会形成奇环。
由于我们只需要维护奇偶性,可以直接用异或操作。
时间复杂度 O ( n log 2 n ) O(n\log^2n) O(nlog2n)。
code
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
typedef pair<int,int> Pair;
int n,m,T;
int fa[N],ans[N],Rank[N],val[N];
struct node{
Pair del;bool flag;
node(Pair _del,bool _flag):del(_del),flag(_flag){}
};
vector<Pair>e[N<<2];
vector<node>op[N<<2];
void Modify(int root,int l,int r,int x,int y,int u,int v){
if(l>=x&&r<=y){
return e[root].push_back(make_pair(u,v));
}
int mid=(l+r)>>1;
if(x<=mid) Modify(root<<1,l,mid,x,y,u,v);
if(y>mid) Modify(root<<1|1,mid+1,r,x,y,u,v);
}
int find(int &x){
int now=0;
while(x!=fa[x]) now^=val[x],x=fa[x];
return now;
}
void Query(int root,int l,int r){
bool flag=true,now;
for(int i=0;i<e[root].size();++i){
int x=e[root][i].first,y=e[root][i].second,u=find(x),v=find(y);
if(x==y){
if(!(u^v)){
flag=false;
for(int i=l;i<=r;++i) ans[i]=0;
break;
}
continue;
}
if(Rank[x]<Rank[y]) swap(x,y);
fa[y]=x,val[y]=u^v^1,now=0;
if(Rank[x]==Rank[y]) ++Rank[x],now=1;
op[root].push_back(node(make_pair(x,y),now));
}
int mid=(l+r)>>1;
if(l!=r&&flag) Query(root<<1,l,mid),Query(root<<1|1,mid+1,r);
for(int i=op[root].size()-1;~i;--i){
int x=op[root][i].del.first,y=op[root][i].del.second;
fa[y]=y,val[y]=0,Rank[x]-=op[root][i].flag;
}
}
int main(){
int u,v,l,r;
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;++i) fa[i]=i,ans[i]=Rank[i]=1;
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&u,&v,&l,&r);
if(l<r) Modify(1,1,T,l+1,r,u,v);
}
Query(1,1,T);
for(int i=1;i<=T;++i) puts(ans[i]?"Yes":"No");
return 0;
}