BZOJ 4025 二分圖 分治+並查集

BZOJ 4025 二分圖 分治+並查集

題目大意：給定一張n個點的圖，有m條邊，T個時間段，每條邊只存在於(st,ed]這些時間段，求每個時間段內這個圖是否是二分圖
分治並查集大法好
定義Solve(x,y,E)為當前處理的區間為[x,y]，E為所有存在時間為[x,y]的子集的邊的集合
那麼對於E中的每一條邊(u,v)，討論：
若當前邊的存在時間為[x,y]，則在並查集上判斷是否出現奇環
如果出現，[x,y]內的所有時刻都一定不是二分圖，輸出答案即可
如果不出現，在並查集中連接(u,v)
否則判斷存在時間和mid的關系討論扔進左區間還是右區間還是都扔進去
並查集不需要可持久化，只需要記錄進行過的操作，在回溯的時候復原即可
注意並查集不要寫路徑壓縮，因為路徑壓縮的優化是均攤的，均攤在分治這種樹形結構上使用是無效的，只寫按秩合並就行了
時間復雜度O(mlog2n)
然而跑的比O(mlogn)的LCT還快是什麼鬼……

#include 
#include 
#include 
#include 
#include 
#define M 100100
using namespace std;

struct edge{
    int x,y;
    int st,ed;
    edge() {}
    edge(int _,int __,int ___,int ____):
        x(_),y(__),st(___),ed(____) {}
};

int n,m,T;
int stack[M<<2],top;
//若x<0 代表x的rank被加了1
//若x>0 表示x的父親被修改了 

namespace Union_Find_Set{
    int fa[M],rank[M],a[M];
    int Find(int x)
    {
        while(fa[x]!=x)
            x=fa[x];
        return fa[x]=x;
    }
    int Distance(int x)
    {
        int re=0;
        while(fa[x]!=x&&fa[x])
            re^=a[x],x=fa[x];
        return re;
    }
    void Union(int x,int y,int z)
    {
        x=Find(x);y=Find(y);
        if(x==y) return ;
        if(rank[x]>rank[y])
            swap(x,y);
        if(rank[x]==rank[y])
            rank[y]++,stack[++top]=-y;
        fa[x]=y;a[x]=z;stack[++top]=x;
    }
    void Restore(int bottom)
    {
        while(top>bottom)
        {
            if(stack[top]<0)
                rank[-stack[top]]--;
            else
                fa[stack[top]]=stack[top],a[stack[top]]=0;
            top--;
        }
    }
}

void Divid_And_Conquer(int x,int y,vector &e)
{
    using namespace Union_Find_Set;
    vector::iterator it;
    int i,mid=x+y>>1,bottom=top;
    vector l,r;
    for(it=e.begin();it!=e.end();it++)
    {
        if(it->st==x&&it->ed==y)
        {
            int _x=Find(it->x);
            int _y=Find(it->y);
            int _z=Distance(it->x)^Distance(it->y)^1;
            if(_x!=_y)
                Union(_x,_y,_z);
            else if(_z&1)
            {
                for(i=x;i<=y;i++)
                    puts("No");
                Restore(bottom);
                return ;
            }
        }
        else if(it->ed<=mid)
            l.push_back(*it);
        else if(it->st>mid)
            r.push_back(*it);
        else
            l.push_back(edge(it->x,it->y,it->st,mid)),r.push_back(edge(it->x,it->y,mid+1,it->ed));
    }
    if(x==y)
        puts("Yes");
    else
        Divid_And_Conquer(x,mid,l),Divid_And_Conquer(mid+1,y,r);
    Restore(bottom);
}

int main()
{
    //freopen("4025.in","r",stdin);
    //freopen("4025.out","w",stdout);
    int i;
    edge e;
    vector v;
    cin>>n>>m>>T;
    for(i=1;i<=n;i++)
        Union_Find_Set::fa[i]=i;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&e.x,&e.y,&e.st,&e.ed);
        e.st++;
        if(e.st>e.ed)
            continue;
        v.push_back(e);
    }
    Divid_And_Conquer(1,T,v);
    return 0;
}