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

Problem

二分图

Description

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

Input

输入数据的第一行是三个整数。
第行到第行，每行4个整数，表示第条边连接两个点，这条边在时刻出现，在第时刻消失。

Output

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

Sample Input

Sample Output

1
2
3

Yes
No
Yes

Explanation

时刻，出现两条边和。
第时间段内，这个图是二分图，输出。
时刻，出现一条边。
第时间段内，这个图不是二分图，输出。
时刻，和两条边消失。
第时间段内，只有一条边，这个图是二分图，输出。

HINT

，，，，。

标签：线段树分治 并查集

Solution

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

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

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

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

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;
}