题面

Solution

这种每条边出现在一段区间的题，我们可以先考虑使用线段树分治来搞。这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，我们考虑如何维护一个图是否为二分图的问题。我们知道，一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶数。知道这一点之后，我们考虑用并查集处理这个问题。对于没有环的时候，我们直接连上就好。对于有环的时候，我们就需要知道这两个点的距离是奇数还是偶数。如果是奇数的，说明之后无论在怎么连，这个图一定gg了，直到这条边取消位置；如果是偶数的，说明这个环是合法的，之后无论有什么边接到这个环上，我们当前这条新插入的边都不会有任何影响。因此，如果一条边会连城环，无论如何，这条边都不会被加上。所以说，我们这里维护的东西是一个生成树。我们考虑用并查集维护这个生成树。因为我们这里是按秩合并的并查集，失去了原来的树的结构。因此，我们考虑在每个点上维护它到它的父亲的真实距离。我们在连接两个点的时候，我们在并查集上肯定是连接这两个点所在并查集的父亲。这时候，这两个父亲的真实距离一定为这两个点到父亲的真实距离和+1，(这里我们的真实距离和直接暴力算即可，因为并查集按秩合并时，高度不会太大)。我们查询的时候我们算的是它们两个点到并查集的LCA的真实距离，因为并查集的LCA不一定是它们在原树中的LCA，因此我们这里按真实距离算出来的距离并非它们两的真实距离。但是，我们会发现这里多算的距离一定是2的倍数(两个点同时经过一条边)，因此，我们的奇偶性质还是正确的。时间复杂度$O(nlog^2n)$ 就酱，我们就可以切掉这道题啦ヾ(◍°∇°◍)ﾉﾞ

Code

//BZOJ 4025 二分图
//线段树二分+并查集妙题
//Mar,25th,2019
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=100000+100;
struct edge
{
    int s,t;
    edge (int x,int y)
    {
        s=x,t=y;
    }
};
struct UnF
{
    int fa[N],size[N],dis[N],depth[N],top,mstack[N*20];
    void Init(int n)
    {
        for(int i=1;i<=n;i++)
            depth[i]=size[i]=1;
    }
    int GetFa(int x,int &w)
    {
        if(fa[x]==0) 
        {
            w++;
            return x;
        }
        int t=GetFa(fa[x],w+=dis[x]+1);
        depth[x]=depth[fa[x]]+1;
        return t;
    }
    int LCA(int x,int y,int &w)
    {
        w=1;
        if(depth[x]<depth[y]) swap(x,y);
        while(depth[x]>depth[y])
            w+=dis[x]+1,x=fa[x];
        if(x==y) return x;
        w++;
        while(fa[x]!=fa[y])
        {
            w+=dis[x]+1,w+=dis[y]+1;
            x=fa[x],y=fa[y];
        }
        w+=dis[x]+dis[y]+1;
        return fa[x];
    }
    int Link(int x,int y)
    {
        int d1=0,d2=0,fa1=GetFa(x,d1),fa2=GetFa(y,d2);
        if(size[fa1]>size[fa2])
            swap(x,y),swap(fa1,fa2),swap(d1,d2);
        mstack[++top]=0;
        //cerr<<fa1<<" "<<fa2<<" "<<x<<" "<<y<<" "<<d1<<" "<<d2<<endl;
        if(fa1==fa2)
        {
            int t_d=0;
            LCA(x,y,t_d);
            if(t_d%2==1)
                return 1;
            return 0;
        }
        mstack[top]=fa1;
        dis[fa1]=d1+d2-2,fa[fa1]=fa2,size[fa2]+=size[fa1];
        return 0;
    }
    void Undo()
    {
        if(mstack[top]!=0)
            size[fa[mstack[top]]]-=size[mstack[top]],fa[mstack[top]]=0,
            dis[mstack[top]]=0,depth[mstack[top]]=1;
        top--;
    }
}unf;
int ans[N],top,OK;
struct SegmentTree
{
    #define mid ((now_l+now_r)>>1)
    #define lson (now<<1)
    #define rson (now<<11)
    vector <edge> w[N<<2];
    void Add(int l,int r,edge x,int now,int now_l,int now_r)
    {
        if(now_l>=l and now_r<=r)
        {
            w[now].push_back(x);
            return;
        }
        if(l<=mid) Add(l,r,x,lson,now_l,mid);
        if(r>mid) Add(l,r,x,rson,mid+1,now_r);
    }
    void dfs(int now,int now_l,int now_r)
    {
        int cnt=0;
        for(int i=0;i<int(w[now].size());i++)
            cnt+=unf.Link(w[now][i].s,w[now][i].t);
        OK+=cnt;
        //cerr<<endl;
        //cerr<<now<<" "<<now_l<<" "<<now_r<<" "<<cnt<<endl;
        if(now_l==now_r)
            ans[now_l]=OK;
        else
        {
            dfs(lson,now_l,mid);
            dfs(rson,mid+1,now_r);
        }
        OK-=cnt;
        for(int i=0;i<int(w[now].size());i++)
            unf.Undo();
    }
    #undef mid
    #undef lson
    #undef rson
}sgt;
int n,m,q;
int main()
{
    n=read(),m=read(),q=read();
    unf.Init(n);
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),s=read(),t=read();
        sgt.Add(s+1,t,edge(u,v),1,1,q);
    }
     
    sgt.dfs(1,1,q);
     
    for(int i=1;i<=q;i++)
        if(ans[i]==0)
            printf("Yes\n");
        else
            printf("No\n");
    return 0;
}

[BZOJ 4025] 二分图

题面

Solution

Code