CF576E 笔记

前置知识：线段树分治。

题意

给定一个 \(n\) 个点 \(m\) 个点的图，有 \(k\) 种颜色，初始时每条边都没有颜色。

有 \(q\) 组询问，每组询问 \((i, c)\) 表示把第 \(i\) 条边颜色改成 \(c\)，然后判断：所有颜色为 \(c\) 的边拉出来是否是一个二分图。

如果是就输出 YES；否则输出 NO，并撤销该操作。

\(n, m \le 5 \times 10^5, k \le 50\)

题解

考虑线段树分治。但是在线段树分治时，会有一个问题：无法确定一条边的出现时间。

思考一下线段树分治的性质，可以发现：当在线段树上递归到叶子结点，并处理当前叶子的询问时，前面的询问都被处理过了。就是说，遍历线段树，叶节点的询问一定是 \(1, 2, \cdots, q\) 的顺序被遍历。

于是，考虑同一条边被改的相邻的时间节点 \(x, y\)，这条边会影响到的，只有 \([x + 1, y - 1]\) 中的询问。而递归到结点 \([l, r]\) ( \(x < l \le r < y\) ) 时，因为这个时候拿到的边的颜色是处理了 \([1, l - 1]\) 过后的，所以我们直接连边即可。总复杂度 \(O(n \log^2 n)\)。

代码

code:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1E6 + 5, K = 51;
int n, m, q, k, a[N], c[N], pre[N], nc[N];
pair <int, int> e[N];
stack <pair <pair <int, int>, int>> st;
struct bcj {
  int fa[N], sz[N];
  void init() {
    for (int i = 1; i <= 2 * n; ++i)
      fa[i] = i, sz[i] = 1;
  }
  int find(int x) {return x == fa[x] ? x : find(fa[x]);}
  void merge(int x, int y, int col) {
    x = find(x), y = find(y);
    if (x == y) return ;
    if (sz[x] > sz[y]) swap(x, y);
    st.emplace(make_pair(make_pair(x, y), col));
    fa[x] = y; sz[y] += sz[x];
  }
  void mer(int id, int col) {
    auto [x, y] = e[id];
    merge(x + n, y, col);
    merge(x, y + n, col);
  }
  void cut(int x, int y) {fa[x] = x; sz[y] -= sz[x];}
  bool same(int x, int y) {return find(x) == find(y);}
} f[K];
void cl(int to) {
  while ((int)st.size() > to) {
    auto [x, y] = st.top().first; int c = st.top().second; st.pop();
    f[c].cut(x, y);
  }
}
vector <int> v[N << 1];
void ins(int x, int l, int r, int L, int R, int p) {
  if (l >= L && r <= R) {
    v[x].emplace_back(p);
    return ;
  } int mid = (l + r) >> 1;
  if (L <= mid) ins(x << 1, l, mid, L, R, p);
  if (R > mid) ins(x << 1 | 1, mid + 1, r, L, R, p);
}
int wtf = 0;
void solve(int x, int l, int r) {
  int to = st.size();
  for (auto id : v[x]) {
    if (nc[id]) f[nc[id]].mer(id, nc[id]);
  }
  int mid = (l + r) >> 1;
  if (l == r) {
    int id = a[l]; auto [u, v] = e[id];
    if (f[c[l]].same(u, v)) cout << "NO\n";
    else cout << "YES\n", nc[id] = c[l];
  } else solve(x << 1, l, mid), solve(x << 1 | 1, mid + 1, r);
  cl(to);
}
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  cin >> n >> m >> k >> q;
  for (int i = 0; i <= k; ++i)
    f[i].init();
  for (int i = 1; i <= m; ++i)
    cin >> e[i].first >> e[i].second;
  for (int i = 1; i <= q; ++i) 
    cin >> a[i] >> c[i];
  for (int i = 1; i <= q; ++i) {
    if (pre[a[i]] + 1 <= i - 1)
      ins(1, 1, q, pre[a[i]] + 1, i - 1, a[i]);
    pre[a[i]] = i;
  } 
  for (int i = 1; i <= m; ++i)
    if (pre[i] < q) ins(1, 1, q, pre[i] + 1, q, i);
  solve(1, 1, q);
}