P5787 线段树分治

模板题

每条边有一个生命周期，判断每一时刻这张图是不是二分图。

首先我们可以利用线段树分治和可撤销并查集，递归得到每一时刻的图。

如何利用并查集判断图是否是二分图？

可以扩展一下并查集的域，每个节点有两个版本，一个是 1 集合，一个是 2 集合。每次加边时，合并 1 集合中的 u 点和 2 集合中的 v 点以及 1 集合中的 v 点 和 2 集合的 u 点。

每次查询，如果两个 1 集合（或两个 2 集合）中的点连通，那么此时二分图就不存在，不需要递归到底，答案默认为 false，当递归到底时，此时的答案就是 true。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k;
vector<bool> ans;
#define fi first
#define se second
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;

class DSU {
  vector<int> pa, sz;
  stack<int> s;

public:
  void init(int n) {
    pa.resize(n * 2 + 1), sz.assign(n * 2 + 1, 1);
    iota(pa.begin(), pa.end(), 0);
  }
  int find(int x) { return x == pa[x] ? x : find(pa[x]); }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)
      return;
    if (sz[x] < sz[y])
      swap(x, y);
    s.push(y);
    pa[y] = x;
    sz[x] += sz[y];
  }
  bool add(int u, int v, int n) {
    int ru = find(u), rv = find(v);
    if (ru == rv)
      return false;
    unite(u, v + n);
    unite(v, u + n);
    return true;
  }
  int get_time() { return s.size(); }
  void roll_back(int time) {
    while (s.size() > time) {
      int y = s.top(), x = pa[y];
      s.pop();
      sz[x] -= sz[y];
      pa[y] = y;
    }
  }
} dsu;

vector<vector<pii>> tr;

void insert(int p, int l, int r, int pl, int pr, int u, int v) {
  if (pl <= l && r <= pr) {
    tr[p].emplace_back(u, v);
    return;
  }
  int mid = (l + r) >> 1;
  if (pl <= mid)
    insert(p << 1, l, mid, pl, pr, u, v);
  if (pr > mid)
    insert(p << 1 | 1, mid + 1, r, pl, pr, u, v);
}
void dfs(int p, int l, int r) {
  int time = dsu.get_time();
  bool ok = true;
  for (auto [u, v] : tr[p]) {
    if (!dsu.add(u, v, n)) {
      ok = false;
      break;
    }
  }
  if (ok) {
    if (l == r) {
      ans[l] = true;
    } else {
      int mid = (l + r) >> 1;
      dfs(p << 1, l, mid);
      dfs(p << 1 | 1, mid + 1, r);
    }
  }
  dsu.roll_back(time);
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> k;
  dsu.init(n + 1);
  ans.assign(k + 1, false);
  tr.resize(4 * k + 1);
  for (int i = 0, x, y, l, r; i < m; i++) {
    cin >> x >> y >> l >> r;
    insert(1, 0, k - 1, l, r - 1, x, y);
  }
  dfs(1, 0, k - 1);
  for (int i = 0; i < k; i++)
    cout << (ans[i] ? "Yes" : "No") << '\n';
  return 0;
}