Description

洛谷

翻译可能有点不太明白。其实这里的加边和删边是原来有边就删，没有就加。

然后这里保证了 \(ui<vi\)，所以边是不会有正反情况的。

Solution

第一次写带权并查集，连蒙带抄把它应该搞懂了。

我们可以用线段树分治来优化，具体做法就是将每条边存在的时间化成一个区间挂在线段树上，因为大区间包含的小区间一定包含大区间的边，所以我们可以只在大区间加边，再将边的信息插入到并查集后遍历小区间，回退时删掉这个区间加的边即可。

具体讲一下带权并查集的写法。这里的权值就是 \(1\)，\(0\)。

\(unoinSet\)

void unionSet(const int u, const int v, const bool flag) {
    int x = findSet(u), y = findSet(v);
    if(dep[x] < dep[y]) swap(x, y);
    if(dep[x] == dep[y]) ++ dep[x], s[++ tp] = -x;
    f[y] = x; s[++ tp] = y; c[y] = flag;
}

这其实就是按秩合并。因为要回退，我们又有两种更改的操作，所以把一种操作的栈赋值负数。而 \(c\) 就是维护是否相同。（如果原本相同就需要更改）

\(Restore\)

void Restore(const int ntp) {
    int u;
    while(tp > ntp) {
        u = s[tp]; -- tp;
        if(u > 0) f[u] = u, c[u] = 0;
        else -- dep[-u];
    }
}

\(ntp\) 就是这一个区间之前所插入边的个数，我们只用删加的边。其实就是上面的还原。

我们关注到一个重要的点：这个并查集不能用路径压缩。具体就是删除的时候可能会只将根节点的父亲赋值为自己，这个节点的子孙还是和另外一棵树藕断丝连。

Code

#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#define push make_pair
using namespace std;
typedef pair <int, int> Pair;

const int N = 100005;

int n, q, f[N], c[N], dep[N], s[N], tp;
map <Pair, int> mp;
vector <Pair> t[N << 2];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < ‘0‘ || s > ‘9‘) if(s == ‘-‘) f = -1;
    while(s >= ‘0‘ && s <= ‘9‘) {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

int findSet(const int x) {return x == f[x] ? x : findSet(f[x]);}

int dis(const int x) {return x == f[x] ? 0 : (dis(f[x]) ^ c[x]);}

void unionSet(const int u, const int v, const bool flag) {
    int x = findSet(u), y = findSet(v);
    if(dep[x] < dep[y]) swap(x, y);
    if(dep[x] == dep[y]) ++ dep[x], s[++ tp] = -x;
    f[y] = x; s[++ tp] = y; c[y] = flag;
}

void Restore(const int ntp) {
    int u;
    while(tp > ntp) {
        u = s[tp]; -- tp;
        if(u > 0) f[u] = u, c[u] = 0;
        else -- dep[-u];
    }
}

void modify(const int o, const int l, const int r, const int L, const int R, const Pair p) {
    if(l > R || r < L) return;
    if(l >= L && r <= R) {t[o].push_back(p); return;}
    int mid = l + r >> 1;
    modify(o << 1, l, mid, L, R, p); modify(o << 1 | 1, mid + 1, r, L, R, p);
}

void dfs(const int o, const int l, const int r) {
    int ntp = tp;
    for(int i = 0, siz = t[o].size(); i < siz; ++ i) {
        int u = t[o][i].first, v = t[o][i].second;
        bool flag = (dis(u) ^ dis(v) ^ 1);
        if(findSet(u) == findSet(v)) {
            if(flag) {
                for(int j = l; j <= r; ++ j) puts("NO");
                Restore(ntp); return;
            }
        }
        else unionSet(u, v, flag);
    }
    if(l == r) {puts("YES"); Restore(ntp); return;}
    int mid = l + r >> 1;
    dfs(o << 1, l, mid); dfs(o << 1 | 1, mid + 1, r);
    Restore(ntp);
}

void makeSet() {for(int i = 1; i <= n; ++ i) f[i] = i;}

int main() {
    int u, v;
    n = read(), q = read();
    makeSet();
    for(int i = 1; i <= q; ++ i) {
        u = read(), v = read();
        if(mp.count(push(u, v))) modify(1, 1, q, mp[push(u, v)], i - 1, push(u, v)), mp.erase(push(u, v));
        else mp[push(u, v)] = i;
    }
    for(map <Pair, int> :: iterator it = mp.begin(); it != mp.end(); ++ it) modify(1, 1, q, it -> second, q, it -> first);
    dfs(1, 1, q);
    return 0;
}

CodeForces - 813F Bipartite Checking

原文：https://www.cnblogs.com/AWhiteWall/p/12893957.html