BZOJ 4025: 二分图

线段树分治+按秩合并的并查集解决加边删边的问题。
一个图是二分图当且仅当点数大于等于二并且不存在奇环。
那么可以用带权并查集维护路径长度，会出现环就是当加入一条边是产生环并且原路径长度为偶数。

#include <bits/stdc++.h>

namespace IO {
    void read() {}
    template<class T, class... T2>
    void read(T &x, T2 &... oth) {
        x = 0; T f = 1; char ch = getchar();
        while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
        x *= f;
        read(oth...);
    }
}

const int N = 2e5 + 7;

int st[N], top;

struct DSU {
    int fa[N], d[N], dep[N];
    void init(int n) {
        for (int i = 0; i <= n; i++)
            fa[i] = i, d[i] = dep[i] = 0;
    }
    int getfa(int x) {
        while (x != fa[x]) 
            x = fa[x];
        return x;
    }
    int getdis(int x) {
        int dis = 0;
        while (x != fa[x])
            dis ^= d[x], x = fa[x];
        return dis;
    }
    bool merge(int x, int y) {
        int D = getdis(x) ^ getdis(y) ^ 1;
        x = getfa(x), y = getfa(y);
        if (x == y) return D == 0;
        if (dep[x] < dep[y]) 
            std::swap(x, y);
        if (dep[x] == dep[y])
            dep[x]++, st[++top] = -x;
        fa[y] = x; d[y] = D; st[++top] = y;
        return 1;
    }
    void del(int tp) {
        while (top > tp) {
            int x = st[top--];
            if (x < 0)
                dep[-x]--;
            else 
                fa[x] = x, d[x] = 0;
        }
    }
} dsu;

int n, m, T;
struct P {
    int u, v, x, y;
} p[N];
int ans[N];

void solve(int l, int r, const std::vector<int> &vec) {
    int tp = top;
    int mid = l + r >> 1;
    std::vector<int> L, R;
    for (int i = 0, sz = vec.size(); i < sz; i++) {
        int id = vec[i];
        if (p[id].x <= l && r <= p[id].y) {
            if (!dsu.merge(p[id].u, p[id].v)) {
                for (int j = l; j <= r; j++)
                    ans[j] = 1;
                dsu.del(tp);
                return;
            }
        } else {
            if (p[id].x <= mid)
                L.push_back(id);
            if (p[id].y > mid)
                R.push_back(id);
        }
    }
    if (l == r) {
        dsu.del(tp);
        return;
    }
    solve(l, mid, L);
    solve(mid + 1, r, R);
    dsu.del(tp);
}

int main() {
    IO::read(n, m, T);
    dsu.init(n);
    std::vector<int> vec;
    for (int i = 1; i <= m; i++)
        IO::read(p[i].u, p[i].v, p[i].x, p[i].y), p[i].x++, vec.push_back(i);
    solve(1, T, vec);
    for (int i = 1; i <= T; i++)
        puts(ans[i] ? "No" : "Yes");
    return 0;
}

BZOJ 4025: 二分图

原文：https://www.cnblogs.com/Mrzdtz220/p/12275943.html