BZOJ4537/LOJ2048/luogu3247 - 【 HNOI2016 】最小公倍数

题意：

给定一张 $n$ 个顶点 $m$ 条边的无向图 ( 顶点编号为 $1,2,\ldots,n$ )，每条边上带有权值。所有权值都可以分解成 $2^a \times 3^b$ 的形式。

现在有 $q$ 个询问，每次询问给定四个参数 $u$ 、 $v$ 、 $a$ 和 $b$ ，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径（不一定为简单路径），使得路径依次经过的边上的权值的最小公倍数为 $2 ^ a \times 3 ^ b$

$1 \le n,q \le 50000、1 \le m \le 100000、0 \le a,b \le 10^9$

题解：

显然询问的是是否存在一条路径 $max_a = a, max_b = b$ 。

因为不是简单路径，所以可以视作连通分量。

而且一个询问 Q 有解当且仅当将所有 $a \le Q_a, b \le Q_b$ 的边相连， $u$ , $v$ 连通且 $max_a = Q_a, max_b = Q_b$ 。

因为没有更好的方法（233），考虑分块。

二维分块一般按照一维分块 ( 排序后，每块 $sz$ 个元素 )，块内按照第二维排序。

这里按照边 $a$ 排序并分块。

分完块之后找到每一块 $a$ 值的范围 $[l, r]$ 。有个细节，如果有一个 $a$ 跨越了两个块，应该记在后面。将询问插入 $a$ 值的相应块中。

考虑块 $[l, r]$ , 首先需要将 $a_i < l$ 的边按照 $b$ 排序。对于每个询问 $q_j$ ，在 $a_i < l$ 的边中找到 $b_i \le b_{q_j}$ 的边。因为已经按 $b$ 递增，所以用一个指针扫过去，用并查集维护。

对于 $a_i \in [l, r]$ 的边，每次询问暴力扫一遍，将合法的插入并查集。因为完成每次询问后需要将它们清除，所以需要可撤销并查集（只按秩合并，不路径压缩，并记录操作，维护 $max_a, max_b$ ）。

复杂度 $O(sz \log n + \frac{n}{sz} \log n)$ ，但块大小不是设 $\sqrt{n}$ 最优。请自行尝试块大小。

Code

struct Edge {
  int u, v, a, b, id;
}edge[MAXM];
int n, m, q;
typedef Edge Query;
Query query[MAXQ];
inline bool cmpa(Edge a, Edge b) {
  return a.a < b.a;
}
inline bool cmpb(Edge a, Edge b) {
  return a.b < b.b;
}
namespace solver1 {
  namespace dsu {
    int fa[MAXN], sz[MAXN];
    int maxa[MAXN], maxb[MAXN];
    typedef Edge Opt;
    Opt opt[MAXM];
    int cnto;
    void init() {
      for (int i = 1; i <= n; i++) {
        fa[i] = i;
        maxa[i] = -1;
        maxb[i] = -1;
        sz[i] = 1;
      }
    }
    inline void reset() { cnto = 0; }
    inline int find(int x) {
      while(fa[x] != x) x = fa[x];
      return x;
    }
    void unite(Edge e) {
      int u = find(e.u), v = find(e.v);
      if (sz[u] < sz[v]) std::swap(u, v);
      opt[++cnto] = (Opt) {u, v, maxa[u], maxb[u], sz[u]};
      fa[v] = u;
      if (u != v) sz[u] += sz[v];
      maxa[u] = std::max(maxa[u], std::max(maxa[v], e.a));
      maxb[u] = std::max(maxb[u], std::max(maxb[v], e.b));
    }
    void undo() {
      while(cnto) {
        int u = opt[cnto].u, v = opt[cnto].v, a = opt[cnto].a, b = opt[cnto].b;
        fa[v] = v;
        maxa[u] = a;
        maxb[u] = b;
        sz[u] = opt[cnto].id;
        cnto--;
      }
    }
    inline bool ok(Query e) {
      int u = find(e.u), v = find(e.v);
      if (u != v) return 0;
      return maxa[u] == e.a && maxb[u] == e.b;
    }
  }
  void main() {
    int block_sz = sqrt(m * log2(n));
    
    std::sort(edge + 1, edge + m + 1, cmpa);
    std::sort(query + 1, query + q + 1, cmpa);
    static bool ans[MAXQ];
    int curq = 1, lastq = 1;
    for (int l = 1; l <= m; l += block_sz) {
      int r = std::min(l + block_sz - 1, m);
      while(curq <= q && query[curq].a < edge[r].a) curq++;
      if (r == m) curq = q + 1;
      
      std::sort(edge + 1, edge + l, cmpb);
      std::sort(query + lastq, query + curq, cmpb);
      
      int taile = 1;
      dsu::init();
      for (int j = lastq; j < curq; j++) {
        while(taile < l && edge[taile].b <= query[j].b) {
          dsu::unite(edge[taile++]);
        }
        dsu::reset();
        for (int k = l; k <= r; k++) {
          if (edge[k].a <= query[j].a && edge[k].b <= query[j].b) {
            dsu::unite(edge[k]);
          }
        }
        ans[query[j].id] = dsu::ok(query[j]);
        dsu::undo();
      }
      lastq = curq;
    }
    for (int i = 1; i <= q; i++) {
      puts(ans[i] ? "Yes" : "No");
    }
  }
}

BZOJ4537/LOJ2048/luogu3247 - 【 HNOI2016 】 最小公倍数

题意：

题解：

Code

BZOJ4537/LOJ2048/luogu3247 - 【 HNOI2016 】最小公倍数