BZOJ4025 二分图

题意：

题目链接

思路：

首先\(此图是二分图\)与\(此图没有奇环\)是充分必要关系
那么，如何判断一个图是否有奇环呢？
两种方法：一是黑白染色，二是带权并查集
但黑白染色每一次都是\(O(n)\)的，无法优化
于是就用带权并查集
最暴力的做法是每一个时间点都\(O(n)\)做一次，显然不行
然而我们发现，每一次其实都只有一条边出现或消失
于是我们想可不可以用某种方法最小化重复计算次数？
其实可以用线段树。
在时间轴上建立一棵线段树
对于每条边出现时间与消失时间，可以类似地在线段树上进行区间操作
然后遍历整棵线段树，到相应节点进行相应操作，到叶子节点统计答案回溯
其实这种思想称为线段树分治

具体实现：

在线段树每个节点上挂一个\(vector\),区间操作时记在\(vector\)上面即可
遍历时因为回溯要撤销，所以这就要求并查集可以撤销
于是就只能用启发式合并的并查集
时间复杂度\(O(nlog^2n)\)

注意事项：

积累一下用带权并查集判奇环的小技巧

code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
int n,m,t,top,fa[N],siz[N],dis[N];
int t1[M],t2[M];
struct Seg_tree{int l,r;vector<pair<int,int> >e;}tr[N<<2];
inline int read()
{
    int s=0,w=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return s*w;
}
int fd(int x)
{
    return fa[x]==x?x:fd(fa[x]);
}
int dist(int x)
{
    return fa[x]==x?0:dist(fa[x])^dis[x];
}
void build(int rt,int l,int r)
{
    tr[rt].l=l,tr[rt].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
}
void update(int rt,int l,int r,int u,int v)
{
    if(l<=tr[rt].l&&tr[rt].r<=r)
    {
        tr[rt].e.push_back(make_pair(u,v));
        return;
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    if(l<=mid) update(rt<<1,l,r,u,v);
    if(mid<r) update(rt<<1|1,l,r,u,v);
}
inline void cancel()
{
    siz[t1[top]]-=siz[t2[top]];
    fa[t2[top]]=t2[top];
    dis[t2[top]]=0;
    --top;
}
void solve(int rt,int l,int r)
{
    int num=0;
    for(int i=0;i<tr[rt].e.size();++i)
    {
        int u=tr[rt].e[i].first,v=tr[rt].e[i].second;
        int a=fd(u),b=fd(v);
        if(a==b)
        {
            int x=dist(u)^dist(v)^1;
            if(x) 
            {
                for(int i=l;i<=r;++i) puts("No");
                while(num--)cancel();
                return;
            }
        }
        else
        {
            if(siz[a]<siz[b]) swap(a,b);
            siz[a]+=siz[b];fa[b]=a;
            dis[b]=dist(v)^dist(u)^1;++num;
            t1[++top]=a,t2[top]=b;
        }
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    if(l==r) puts("Yes");
    else{solve(rt<<1,l,mid);solve(rt<<1|1,mid+1,r);}
    while(num--)cancel();
}
int main()
{
    n=read(),m=read(),t=read();
    for(int i=1;i<=n;++i)fa[i]=i,siz[i]=1,dis[i]=0;
    build(1,1,t);
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read(),st=read()+1,ed=read();
        if(st<=ed)update(1,st,ed,u,v);
    }
    solve(1,1,t);
    return 0;
}

BZOJ4025 二分图

原文：https://www.cnblogs.com/zmyzmy/p/12178021.html