BZOJ4025二分图传送门

Description

神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。

Input

输入数据的第一行是三个整数n,m,T。

第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这条边在start时刻出现，在第end时刻消失。

Output

输出包含T行。在第i行中，如果第i时间段内这个图是二分图，那么输出“Yes”，否则输出“No”，不含引号。

Sample Input

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2

Sample Output

Yes
No
Yes

Solution

经典的CDQ嵌套数据结构

对于一条边，若它的存在区间为(L,R);

若在CDQ时，一条边横跨整个区间，则将这条边的影响加入到当前数据结构中

若该边在左侧，则将它放在加入左侧的队列，右侧同；

若该边横跨mid，则将它拆为(L,mid),(mid+1,R);

搞完了以后，再处理左右区间，处理完后，还原数据结构

本题维护是否有奇环，用并查集，判定是否两个点到图中一个点（并查集的根）距离是否为奇

#include<stdio.h>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int N=200005;
 
typedef pair<int,int> pii;
stack<pii>Ops;
int Fa[N],Size[N],D[N];
int GetFa(int x){
    while(Fa[x]!=x)x=Fa[x];
    return x;
}
int GetDis(int x){
    int d=0;
    while(Fa[x]!=x)d^=D[x],x=Fa[x];
    return d;
}
void Merge(int x,int y,int z){
    int fx=GetFa(x),fy=GetFa(y);
    if(fx==fy)return;
    if(Size[x]>Size[y])swap(x,y);
    if(Size[x]==Size[y])
        Size[y]++,Ops.push(pii(1,y));
    Fa[x]=y;D[x]=z;Ops.push(pii(2,x));
}
void Recovery(int x){
    while(Ops.size()>x){
        pii tmp=Ops.top();
        Ops.pop();
        if(tmp.first==1)Size[tmp.second]--;
        else Fa[tmp.second]=tmp.second,D[tmp.second]=0;
    }
}
 
int n,m,T;
bool Ans[N];
struct Edge{
    int x,y,l,r;
};
vector<Edge>v;
typedef vector<Edge>::iterator vi;
void CDQ(int l,int r,vector<Edge>e){
    int mid=l+r>>1,now=Ops.size();
    vector<Edge> v1,v2;
    for(vi it=e.begin();it!=e.end();it++){
        if(it->l==l&&it->r==r){
            int x=GetFa(it->x),y=GetFa(it->y);
            int z=GetDis(it->x)^GetDis(it->y)^1;
            if(x!=y)Merge(x,y,z);
            else if(z&1){
                Recovery(now);
                return;
            }
        }
        else if(it->r<=mid)v1.push_back(*it);
        else if(it->l>mid)v2.push_back(*it);
        else {
            v1.push_back((Edge){it->x,it->y,it->l,mid});
            v2.push_back((Edge){it->x,it->y,mid+1,it->r});
        }
    }
    if(l==r) Ans[l]=1; 
    else CDQ(l,mid,v1),CDQ(mid+1,r,v2);
    Recovery(now);
}
int main(){
    int i,j,k,x,y;
    scanf("%d%d%d",&n,&m,&T);
    for(i=1;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&j,&k);
        j++;
        if(j>k)continue;
        v.push_back((Edge){x,y,j,k});
    }
    for(i=1;i<=n;i++)Fa[i]=i;
    CDQ(1,T,v);
    for(i=1;i<=T;i++)
        if(Ans[i])puts("Yes");
        else puts("No");
}

BZOJ4025二分图 传送门