洛谷P3247 [HNOI2016]最小公倍数题解

题目链接：P3247 [HNOI2016]最小公倍数

题意：

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

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

注意：路径可以不是简单路径。

输入格式：

输入文件的第一行包含两个整数 \(N\) 和 \(M\)，分别代表图的顶点数和边数。

接下来 \(M\) 行，每行包含四个整数 \(u,v,a,b\) 代表一条顶点 \(u\) 和 \(v\) 之间、权值为 \(2^a\times 3^b\) 的边。

接下来一行包含一个整数 \(q\)，代表询问数。

接下来 \(q\) 行，每行包含四个整数 \(u,v,a\) 和 \(b\)，代表一次询问。询问内容请参见问题描述。

输出格式：

对于每次询问，如果存在满足条件的路径，则输出一行 Yes，否则输出一行 No（注意：第一个字母大写，其余字母小写）。

数据范围：

\(1\le n,q\le 5\times 10^4\)，\(1\leq m\leq 10^5\)，\(0\leq a,b\leq 10^9\)。

注意到能用的边两种权值一定不超过询问的 \(a,b\) ，考虑离线询问，用并查集维护连通性，然后判断下最大值。

考虑将边按照 \(a\) 排序并分块，并将询问插到最后一个不超过它的块内，钦定其有用的边为到目前为止所有的块。

此时 \(a\) 的顺序已经搞定了，因此只要考虑 \(b\) 。依次考虑当前块的询问：

对于处理完的块，直接把不超过 \(b\) 的边塞到并查集，这里需要一个排序。
对于每个块，暴力找边，然后跑一遍 BFS。

设块的大小为 \(S\) ，则时间复杂度为 \(\mathcal{O}\left(\left(qS + \frac{m^2}{S}\right)\alpha(n)\right)\) ，取 \(S = \mathcal{O}\left(\frac{m}{\sqrt{q}}\right)\)

最终时间复杂度 \(\mathcal{O}\left(m \sqrt{q} \alpha(n)\right)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e4 + 15))
#define M ((int)(1e5 + 15))

char ans[N],vis[N],used[N]; queue<int> que;
int n,m,Q,S,blocks,fa[N],mxa[N],mxb[N],stk[N];
struct Edge { int u,v,a,b; } e0[M];
struct cxy { int u,v,a,b,id; };
vector<cxy> query[M]; vector< tuple<int,int,int> > e[N];
int find(int x)
{
    while(fa[x] >= 0 && fa[fa[x]] >= 0)
        x = fa[x] = fa[fa[x]];
    return fa[x] >= 0 ? fa[x] : x;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 0,u,v,a,b; i < m; i++)
    {
        cin >> u >> v >> a >> b;
        e0[i] = {u - 1, v - 1, a, b};
    }
    sort(e0, e0 + m, [](Edge a, Edge b) { return a.a < b.a; });
    cin >> Q; S = 1.5 * m / sqrt(Q); blocks = (m + S - 1) / S;
    for(int i = 0,u,v,a,b; i < Q; i++)
    {
        cin >> u >> v >> a >> b; --u; --v;
        int j = 0; while(j + 1 < blocks && e0[S * j + S - 1].a <= a) ++j;
        query[j].push_back({u,v,a,b,i});
    }
    for(int bl = 0; bl < blocks; bl++)
    {
        memset(fa, -1, (n + 5) * sizeof(int));
        memset(mxa, -1, (n + 5) * sizeof(int));
        memset(mxb, -1, (n + 5) * sizeof(int));
        int i = 0;
        sort(e0, e0 + S * bl, [](Edge a, Edge b) { return a.b < b.b; });
        sort(query[bl].begin(), query[bl].end(), [](cxy a, cxy b) { return a.b < b.b; });
        for(auto q : query[bl])
        {
            for( ;i < S * bl && e0[i].b <= q.b; i++)
            {
                int u = find(e0[i].u), v = find(e0[i].v);
                if(u != v)
                {
                    if(fa[u] > fa[v]) swap(u,v);
                    fa[u] += fa[v]; up(mxa[u], mxa[v]); up(mxb[u], mxb[v]); fa[v] = u;
                }
                up(mxa[u], e0[i].a); up(mxb[u], e0[i].b);
            }
            int top = 0, u = find(q.u), v = find(q.v);
            used[u] = true; stk[top++] = u;
            if(u != v) { used[v] = true; stk[top++] = v; }
            for(int j = S * bl; j < m && j < S * (bl + 1); j++)
                if(e0[j].a <= q.a && e0[j].b <= q.b)
                {
                    int u = find(e0[j].u), v = find(e0[j].v);
                    if(!used[u]) { used[u] = true; stk[top++] = u; }
                    if(!used[v]) { used[v] = true; stk[top++] = v; }
                    e[u].emplace_back(v, e0[j].a, e0[j].b);
                    e[v].emplace_back(u, e0[j].a, e0[j].b);
                }
            while(!que.empty()) que.pop(); int ma = -1, mb = -1;
            for(que.push(u), vis[u] = true; !que.empty(); )
            {
                int u = que.front(); que.pop(); up(ma, mxa[u]); up(mb, mxb[u]);
                for(auto ed : e[u])
                {
                    int v,a,b; tie(v,a,b) = ed; up(ma, a); up(mb, b);
                    if(!vis[v]) { vis[v] = true; que.push(v); }
                }
            }
            ans[q.id] = (vis[v] && ma == q.a && mb == q.b);
            for(int j = 0; j < top; j++) {
                int u = stk[j]; used[u] = vis[u] = false; e[u].clear();
            }
        }
    }
    for(int i = 0; i < Q; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
    return 0;
}