【洛谷P5787】【模板】线段树分治 | Mrsrz's blog

线段树分治

题目大意：

给定 $n$ 个点 $m$ 条边的图，有 $k$ 个时刻。

每条边有一个出现时间段，在这个时间段以外这条边不存在。

对每个时刻，输出这个时刻的图是否是二分图。

题解：

线段树分治，用可撤销并查集维护，判断是否有奇环即可。

每个点记录到并查集上父亲的原图上距离的奇偶性。

可以通过这些信息来判断任意两点的奇偶性。

时间复杂度 $O(m\log n\log k)$。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+5;
pair<int,int>e[N*2];
vector<int>vec[N<<2];
int n,m,t,fa[N],sz[N],dis[N],sta[N],top;
bool isok=1;
inline int find(int x){while(x!=fa[x])x=fa[x];return x;}
inline int dist(int x){int y=0;while(x!=fa[x])y^=dis[x],x=fa[x];return y;}
void add(int l,int r,int o,const int&L,const int&R,const int&id){
    if(L<=l&&r<=R)vec[o].push_back(id);else{
        const int mid=l+r>>1;
        if(L<=mid)add(l,mid,o<<1,L,R,id);
        if(mid<R)add(mid+1,r,o<<1|1,L,R,id);
    }
}
void solve(int l,int r,int o){
    const int TOP=top;const bool OK_=isok;
    for(int i=0;i<vec[o].size();++i){
        const int id=vec[o][i];
        int u=find(e[id].first),v=find(e[id].second);
        int du=dist(e[id].first),dv=dist(e[id].second);
        if(u!=v){
            if(sz[u]<sz[v])swap(u,v);
            fa[v]=u,sz[u]+=sz[v],dis[v]=du^dv^1;
            sta[++top]=v;
        }else
        if((du^dv^1)&1)isok=0;
    }
    if(l==r)cout<<(isok?"Yes":"No")<<'\n';else{
        const int mid=l+r>>1;
        solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
    }
    isok=OK_;
    while(top!=TOP){
        int u=sta[top--];
        dis[u]=0,sz[fa[u]]-=sz[u],fa[u]=u;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>t;
    for(int i=1;i<=m;++i){
        int l,r;
        cin>>e[i].first>>e[i].second>>l>>r;
        --r;
        add(0,t-1,1,l,r,i);
    }
    for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    solve(0,t-1,1);
    return 0;
}