BZOJ4025 二分图 <线段树分治+并查集>

Problem

二分图

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

神犇有一个$n$个节点的图。
因为神犇是神犇，所以在T时间内一些边会出现后消失。
神犇要求出每一时间段内这个图是否是二分图。
这么简单的问题神犇当然会做了，于是他想考考你。

Input

输入数据的第一行是三个整数$n,m,T$。
第$2$行到第$m+1$行，每行4个整数$u,v,start,end$，表示第$i$条边连接$u,v$两个点，这条边在$start$时刻出现，在第$end$时刻消失。

Output

输出包含$T$行。在第$i$行中，如果第$i$时间段内这个图是二分图，那么输出Yes，否则输出No。

Sample Input

3 3 3
1 2 0 2
2 3 0 3
1 3 1 2

Sample Output

Yes
No
Yes

Explanation

$0$时刻，出现两条边$1-2$和$2-3$。
第$1$时间段内，这个图是二分图，输出$Yes$。
$1$时刻，出现一条边$1-3$。
第$2$时间段内，这个图不是二分图，输出$No$。
$2$时刻，$1-2$和$1-3$两条边消失。
第$3$时间段内，只有一条边$2-3$，这个图是二分图，输出$Yes$。

HINT

$n\le10^5$，$m\le2\times10^5$，$T\le10^5$，$1\le u,v\le n$，$0\le start\le end\le T$。

标签：线段树分治 并查集

Solution

事实证明，线段树不仅是一种数据结构，更是一种思想。

先考虑不带存在时间的版本，可以直接用带权并查集维护。

我们将整个时间想成一段线段，那么其中的任意时间段都是一条更短的线段，显然是可以和线段树一样分作$\log{n}$段。那么我们对每条边存在的时间区间做这种拆分，在这$\log{n}$个区间内的并查集中分别加入这条边然后判断询问。

像整体二分一样分治处理即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, T; bool ans[MAX_N+5];
int fa[MAX_N+5], fc[MAX_N+5], w[MAX_N+5];
struct edge {int u, v, l, r;} ;
int getf(int x) {return fa[x] == x ? x : getf(fa[x]);}
int getc(int x) {return fa[x] == x ? 0 : getc(fa[x])^fc[x];}
void merge(int u, int v, int c, stack <int> &sta) {
    if (w[u] < w[v]) swap(u, v);
    sta.push(v), fa[v] = u, fc[v] = c, w[u] += w[v];
}
void restore(stack <int> &sta) {
    for (int u; !sta.empty(); sta.pop())
        u = sta.top(), w[fa[u]] -= w[u], fa[u] = u, fc[u] = 0;
}
void bi_solve(int s, int t, vector <edge> E) {
    vector <edge> El, Er; stack <int> sta;
    for (int i = 0; i < (int)E.size(); i++)
        if (s >= E[i].l && t <= E[i].r) {
            int u = getf(E[i].u), v = getf(E[i].v);
            int c = getc(E[i].u)^getc(E[i].v)^1;
            if (u^v) merge(u, v, c, sta);
            else if (c) {
                for (int j = s; j <= t; j++)
                    ans[j] = false;
                restore(sta); return;
            }
        } else {
            if (E[i].l <= mid) El.push_back(E[i]);
            if (E[i].r >= mid+1) Er.push_back(E[i]);
        }
    if (s < t) bi_solve(s, mid, El), bi_solve(mid+1, t, Er);
    restore(sta);
}
int main() {
    read(n), read(m), read(T); vector <edge> E;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, u, v, l, r; i <= m; i++)
        read(u), read(v), read(l), read(r), 
        E.push_back((edge){u, v, l+1, r});
    for (int i = 1; i <= T; i++) ans[i] = true;
    bi_solve(1, T, E);
    for (int i = 1; i <= T; i++)
        puts(ans[i] ? "Yes" : "No");
    return 0;
}