题解：P7843 「C.E.L.U-03」布尔

· · 题解

考虑限制 s_u 为 x 则 s_v 为 y 同时若 s_v 为 y 则 s_u 为 x 这个是连的双向边，考虑它的逆否命题为 s_u 为 x \oplus 1 则 s_v 为 y \oplus 1 同时若 s_v 为 y \oplus 1 则 s_u 为 x \oplus 1 由此我们可以把这个用并查集来进行缩点判断是否存在合法解。

考虑设 mx_i 表示最大的 r 使得 [i,r] 内的限制能有一组合法解。考虑我们已经知道了 mx_i 那么我们可以预处理倍增数组，定义 f_{i,j} 表示从 i 开始选了 2^j 个区间到的点的位置。故询问可以做到 O(q \log m) 的复杂度。

在这之前我们先考虑新加入一个限制的时候如何判断此时是否合法。设 (u,x) 和 (v,y) 连边 (u,x \oplus 1) 和 (v,y\oplus 1) 连边时存在 (w,0) 和 (w,1) 进行了合并。不妨设 (w,0) 和 (u,x) 在同一个连通块中，易发现由此可得 (u,x \oplus 1) 与 (w,1) 也在同一个连通块中。所以得到 (u,x) 和 (u,x \oplus 1) 在同一个连通块中。最终可得，我们只需要判断 u 和 v 的合法性即可。

考虑如何求解 mx_i 容易发现 mx_i 具有不严格的单调性。易想到可以进行整体二分其中需要用到可撤销并查集 solve(l,r,L,R) 表示求解 [l,r] 之间的答案，答案的范围在 [L,R] 考虑令 mid = \frac{l+r}{2} 求解 mx_{mid} 时我们需要 [mid,L] 扫到 [mid,R] 这种情况我们有个常规优化是进入 solve(l,r,L,R) 时已经将 [r+1,L-1] 的限制处理好。这样才能保证时间复杂度，具体细节见代码。这一部分可以做到 O(m \log n \log m) 的时间复杂度。

总的可以做到 O(q \log m + m \log n \log m) 的时间复杂度。


#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int mx[N], n, m, q, h, t, siz[N], fa[N], c[N][2], tot, f[N][22];

struct A {
  int x, y;
} st[N * 2];

struct S {
  int u, x, v, y;
} a[N];

int find(int x) {
  return (x == fa[x] ? x : find(fa[x]));
}

void merge(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) {
    return;
  }
  if (siz[x] > siz[y]) {
    swap(x, y);
  }
  st[++tot] = {x, y};
  fa[x] = y;
  siz[y] += siz[x];
}

void HS(int x) {
  for (; tot != x; tot--) {
    int x = st[tot].x, y = st[tot].y;
    siz[y] -= siz[x], fa[x] = x;
  }
}

void solve(int l, int r, int L, int R) {
  if (l > r || L > R) {
    return;
  }
  int mid = (l + r) / 2, o = mid - 1;
  int cnt = tot;
  for (int i = mid; i <= min(r, L - 1); i++) {
    int u = a[i].u, v = a[i].v, x = a[i].x, y = a[i].y;
    merge(c[u][x], c[v][y]);
    merge(c[u][!x], c[v][!y]);
  }
  int tmp = tot;
  for (int i = max(L, mid); i <= R; i++) {
    int u = a[i].u, v = a[i].v, x = a[i].x, y = a[i].y;
    int ooo = tot;
    merge(c[u][x], c[v][y]);
    merge(c[u][!x], c[v][!y]);
    if (find(c[u][x]) == find(c[u][!x])) {
      HS(ooo);
      break;
    }
    o = i;
  }
  mx[mid] = o;
  HS(tmp);
  solve(l, mid - 1, L, o);
  HS(cnt);
  for (int i = max(r + 1, L); i <= o - 1; i++) {
    int u = a[i].u, v = a[i].v, x = a[i].x, y = a[i].y;
    merge(c[u][x], c[v][y]);
    merge(c[u][!x], c[v][!y]);
  }
  solve(mid + 1, r, o, R);
  HS(cnt);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n + n; i++) {
    fa[i] = i;
    siz[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    c[i][0] = i;
    c[i][1] = i + n;
  }
  for (int i = 1, u, x, v, y; i <= m; i++) {
    cin >> u >> x >> v >> y;
    a[i] = {u, x, v, y};
  }
  solve(1, m, 1, m);
  for (int i = 1; i <= m; i++) {
    f[i][0] = mx[i] + 1;
  }
  f[m + 1][0] = m + 1;
  for (int j = 1; j <= 20; j++) {
    for (int i = 1; i <= m + 1; i++) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
  }
  for (int l, r; q--;) {
    cin >> l >> r;
    int ans = 0;
    for (int j = 20; j >= 0; j--) {
      if (f[l][j] <= r) {
        l = f[l][j];
        ans += (1 << j);
      }
    }
    if (l <= r) {
      l = f[l][0];
      ans++;
    }
    if (l <= r) {
      cout << -1 << "\n";
    } else {
      cout << ans << "\n";
    }
  }
  return 0;
}