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

Description

给你 $n$ 个布尔变量和 $m$ 个限制，设 $s_i$ 为 $i$ 的取值。第 $i$ 个限制形如 $s_{u_i}$ 为 $x_i$ 则 $s_{v_i}$ 必须为 $y_i$，同时如果 $s_{v_i}$ 为 $y_i$ 则 $s_{u_i}$ 必须取 $x_i$。

一共 $q$ 次询问，每次询问给出一个区间 $l,r$。求最少把 $l,r$ 划分成多少段连续的区间，使得每段里的限制都可以得到一组合法解。如果无论如何都无法得到合法解，输出 -1。

$1\le n\le10^5,1\le m\le6\times10^5,1\le q\le10^6,1\le u,v\le n,1\le l\le r\le m,x,y\in \{0,1\}$。

Solution

首先显然是对于每个 $i$，求出 $nxt_i$ 表示最小的右端点，满足 $[i,nxt_i]$ 合法。

考虑怎么快速判断。容易想到维护拓展域并查集，加入一条边时就分别将 $(u_i,x_i)-(v_i,y_i)$ 和 $(u_i,1-x_i)-(v_i,1-y_i)$ 连边，然后需要判断是否存在一个点 $k$，使得 $(k,0)$ 和 $(k,1)$ 在同一个连通块。

这里有个结论是只需要判断 $(u_i,0)$ 和 $(u_i,1)$ 是否满足条件即可，因为如果 $(k,0)$ 和 $(k,1)$ 在加边同一个连通块，则加边之前 $(k,0)$ 和 $(u_i,x_i)$ 在一个连通块，$(k,1)$ 和 $(v_i,y_i)$ 在一个连通块。由于连边的特殊性，$(u_i,1-x_i)$ 也和 $(k,1)$ 在一个连通块，所以连边后一定满足 $u_i$ 也出现矛盾。

然后线段树分治维护即可。

时间复杂度：$O(m\log n\log m+q\log m)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2e5 + 5, kMaxM = 6e5 + 5;

int n, m, q;
int u[kMaxM], v[kMaxM], x[kMaxM], y[kMaxM], nxt[kMaxM], f[kMaxM][20];
std::vector<int> vec[kMaxM * 4];

struct DSU {
  int fa[kMaxN], rnk[kMaxN];
  std::vector<std::tuple<int, int, int>> stk;
  void init(int n) {
    stk.clear();
    for (int i = 1; i <= n; ++i) fa[i] = i, rnk[i] = 0;
  }
  int find(int x) { return x == fa[x] ? x : find(fa[x]); }
  void unionn(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (rnk[fx] > rnk[fy]) std::swap(fx, fy);
    int det = (rnk[fx] == rnk[fy]);
    fa[fx] = fy, rnk[fy] += det, stk.emplace_back(fx, fy, det);
  }
  void back(int t) {
    for (; stk.size() > t; stk.pop_back()) {
      auto [fx, fy, det] = stk.back();
      fa[fx] = fx, rnk[fy] -= det;
    }
  }
} dsu;

int getid(int x, int op) { return x + op * n; }

void update(int x, int l, int r, int ql, int qr, int id) {
  if (l > qr || r < ql) return;
  else if (l >= ql && r <= qr) return void(vec[x].emplace_back(id));
  int mid = (l + r) >> 1;
  update(x << 1, l, mid, ql, qr, id), update(x << 1 | 1, mid + 1, r, ql, qr, id);
}

void solve(int x, int l, int r) {
  int t = dsu.stk.size();
  for (auto i : vec[x]) {
    dsu.unionn(getid(u[i], ::x[i]), getid(v[i], y[i]));
    dsu.unionn(getid(u[i], ::x[i] ^ 1), getid(v[i], y[i] ^ 1));
  }
  if (l == r) {
    for (int i = std::max(nxt[l - 1] + 1, l); i <= m; ++i) {
      dsu.unionn(getid(u[i], ::x[i]), getid(v[i], y[i]));
      dsu.unionn(getid(u[i], ::x[i] ^ 1), getid(v[i], y[i] ^ 1));
      if (dsu.find(getid(u[i], 0)) == dsu.find(getid(u[i], 1))) {
        nxt[l] = i - 1; break;
      }
    }
    if (!nxt[l]) nxt[l] = m;
    for (int i = nxt[l - 1] + 1; i <= nxt[l]; ++i) update(1, 1, m, l + 1, i, i);
  } else {
    int mid = (l + r) >> 1;
    solve(x << 1, l, mid), solve(x << 1 | 1, mid + 1, r);
  }
  dsu.back(t);
}

int query(int l, int r) {
  int ret = 0;
  for (int i = std::__lg(m); ~i; --i)
    if (f[l][i] <= r)
      l = f[l][i], ret += (1 << i);
  if (f[l][0] <= r) return -1;
  return ret + 1;
}

void dickdreamer() {
  std::cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) std::cin >> u[i] >> x[i] >> v[i] >> y[i];
  dsu.init(2 * n), solve(1, 1, m);
  for (int i = 1; i <= m + 1; ++i) f[i][0] = (i <= m ? nxt[i] + 1 : m + 1);
  for (int i = 1; i <= std::__lg(m); ++i)
    for (int j = 1; j <= m + 1; ++j)
      f[j][i] = f[f[j][i - 1]][i - 1];
  // for (int i = 1; i <= m; ++i) std::cerr << nxt[i] << " \n"[i == m];
  for (int i = 1; i <= q; ++i) {
    // int l, r, ans = 0;
    // std::cin >> l >> r;
    // for (int j = l; j <= r; j = nxt[j] + 1, ++ans) {}
    // std::cout << ans << '\n';
    int l, r;
    std::cin >> l >> r;
    std::cout << query(l, r) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}