BZOJ4025 二分图（线段树分治+并查集）

之前学了一下线段树分治，这还是第一次写。思想其实挺好理解，即离线后把一个操作影响到的时间段拆成线段树上的区间，并标记永久化。之后一块处理，对于某个节点表示的时间段，影响到他的就是该节点一直到线段树根的所有操作。（语死早）这样可以把操作的插入和删除改为只有插入。

具体到这题，由于并查集没法删除边，我们考虑线段树分治。之后要考虑的问题就是如何用并查集判断是否为二分图，也即是否含奇环。假设现在图中有一个偶环，若给偶环两点加了一条边，可以发现无论去掉原偶环上哪一条边都不会改变新出现环的奇偶性。于是我们只要用并查集维护出每个点到根的距离（按秩合并），从而维护出任意两点距离的奇偶性，若加入一条环边则判断是否会构成奇环，有奇环直接退出，没有则扔掉这条边不管。每次处理完线段树一个节点后要把操作还原，以避免影响其他无关节点。这个可以在操作时用栈记录，退出时还原。

这个题就做完了。然而代码能力极差的我发现自己连并查集都差点不会写了。以及，图中会有自环，有自环就不是二分图，我开始竟然反方向判掉了……还有会有出现时刻与消失时刻相同的边，RE了好几发。总之调到吐血，早日退役保平安。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#include<stack>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

int n,m,T,L[N<<],R[N<<],fa[N],deep[N],dis[N],v[N];

struct edge{int x,y;};

struct data{int x,fa,deep,v;};

vector<edge> tree[N<<];

stack<data> undo[N<<];

bool ans[N];

void build(int k,int l,int r)

{

    L[k]=l,R[k]=r;

    if (l==r) return;

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

}

void add(int k,int l,int r,edge e)

{

    if (L[k]==l&&R[k]==r) {tree[k].push_back(e);return;}

    int mid=L[k]+R[k]>>;

    if (r<=mid) add(k<<,l,r,e);

    else if (l>mid) add(k<<|,l,r,e);

    else add(k<<,l,mid,e),add(k<<|,mid+,r,e);

}

int find(int x)

{

    if (fa[x]==x) return x;

    int p=find(fa[x]);

    dis[x]=dis[fa[x]]^v[x];

    return p;

}

void merge(int k,int x,int y,int p)

{

    if (deep[x]<deep[y]) swap(x,y);

    data a;

    a.x=y;a.fa=x;a.deep=deep[x];a.v=v[y];

    undo[k].push(a);

    fa[y]=x;v[y]=p;dis[y]=dis[x]^p;

    if (deep[y]==deep[x]) deep[x]++;

}

void solve(int k)

{

    int s=tree[k].size();

    bool flag=;

    for (int i=;i<s;i++)

    {

        if (tree[k][i].x==tree[k][i].y) {flag=;break;}

        int p=find(tree[k][i].x),q=find(tree[k][i].y);

        if (p!=q) merge(k,p,q,dis[tree[k][i].x]^dis[tree[k][i].y]^);

        else if (dis[tree[k][i].x]^dis[tree[k][i].y]^) {flag=;break;}

    }

    if (L[k]<R[k]&&!flag) solve(k<<),solve(k<<|);

    else if (flag) for (int i=L[k];i<=R[k];i++) ans[i]=;

    while (!undo[k].empty())

    {

        data a=undo[k].top();

        fa[a.x]=a.x;

        deep[a.fa]=a.deep;

        dis[a.x]=v[a.x]=a.v;

        undo[k].pop();

    }

}

int main()

{

    freopen("bzoj4025.in","r",stdin);

    freopen("bzoj4025.out","w",stdout);

    n=read(),m=read(),T=read();

    build(,,T);

    for (int i=;i<=m;i++)

    {

        edge e;e.x=read(),e.y=read();

        int s=read()+,t=read();

        if (s<=t) add(,s,t,e);

    }

    for (int i=;i<=n;i++) fa[i]=i,deep[i]=v[i]=dis[i]=;

    solve();

    for (int i=;i<=T;i++)

    if (ans[i]) printf("No\n");

    else printf("Yes\n");

    fclose(stdin);fclose(stdout);

    return ;

}

秒客网

BZOJ4025 二分图（线段树分治+并查集）

相关文章