洛谷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;
}