正题

题目链接:https://darkbzoj.tk/problem/4025

题目大意

\(n\)个点\(m\)条边，每条边会在一个\(T\)以内的时间段内出现，对于任意一个\(T\)以内的时刻求图是否是一个二分图。

\(1\leq n,T\leq 10^5,1\leq m\leq 2\times 10^5\)

解题思路

插边就暴力插到线段树的对应区间位置，然后考虑怎么判二分图。

可以用扩展域并查集，但是因为要撤回所以不能路径压缩，要用按秩合并。

时间复杂度\(O(n\log^2n )\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=2e5+10;
struct node{
int x,y,d;
}cl[N<<5];
int n,m,T,tot,fa[N],dep[N];
vector<pair<int,int> >e[N<<1];
void Change(int x,int L,int R,int l,int r,pair<int,int> edg){
if(L==l&&R==r){e[x].push_back(edg);return;}
int mid=(L+R)>>1;
if(r<=mid)Change(x*2,L,mid,l,r,edg);
else if(l>mid)Change(x*2+1,mid+1,R,l,r,edg);
else Change(x*2,L,mid,l,mid,edg),Change(x*2+1,mid+1,R,mid+1,r,edg);
return;
}
int find(int x)
{return (fa[x]==x)?x:find(fa[x]);}
void coc(int x,int y){
if(x==y)return;
if(dep[x]>dep[y])swap(x,y);
cl[++tot]=(node){x,y,dep[x]};
fa[y]=x;dep[x]=max(dep[x]+1,dep[y]);
return;
}
bool unionm(int x,int y){
int fx=find(x),Fx=find(x+n);
int fy=find(y),Fy=find(y+n);
if(fx==fy)return 1;
coc(fx,Fy);coc(fy,Fx);
return 0;
}
void ClearTo(int bf){
while(tot>bf){
int x=cl[tot].x,y=cl[tot].y,d=cl[tot].d;
fa[y]=y;dep[x]=d;tot--;
}
return;
}
void Solve(int x,int L,int R){
int bf=tot,flag=0;
for(int i=0;i<e[x].size();i++){
flag|=unionm(e[x][i].first,e[x][i].second);
if(flag)break;
}
if(flag){
for(int i=L;i<=R;i++)
printf("No\n");
ClearTo(bf);return;
}
if(L==R){printf("Yes\n");ClearTo(bf);return;}
int mid=(L+R)>>1;
Solve(x*2,L,mid);
Solve(x*2+1,mid+1,R);
ClearTo(bf);return;
}
int main()
{
freopen("4.in","r",stdin);
freopen("1.ans","w",stdout);
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=m;i++){
int l,r,u,v;
scanf("%d%d%d%d",&u,&v,&l,&r);
if(l==r)continue;
Change(1,1,T,l+1,r,mp(u,v));
}
for(int i=1;i<=2*n;i++)fa[i]=i;
Solve(1,1,T);
return 0;
}