[BZOJ4537][Hnoi2016]最小公倍数（并查集+分块）

Description

　　给定一张 N N 个顶点 MM 条边的无向图（顶点编号为 1,2,…,n 1 , 2 , … , n )，每条边上带有权值。所有权值都可以分解成 2a×3b 2 a × 3 b 的形式。现在有 q q 个询问，每次询问给定四个参数 uu 、 v v 、 aa 和 b b ，请你求出是否存在一条顶点 uu 到 v v 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 2a×3b2a×3b 。注意：路径可以不是简单路径。

　　下面是一些可能有用的定义：

　　最小公倍数： K K 个数 a1,a2,…,aka1,a2,…,ak 的最小公倍数是能被每个 ai a i 整除的最小正整数。

　　路径：路径 P:P1,P2,…,Pk P : P 1 , P 2 , … , P k 是顶点序列，满足对于任意 1≤i<k 1 ≤ i < k ，节点 Pi P i 和 Pi+1 P i + 1 之间都有边相连。

简单路径：如果路径 P:P1,P2,…,Pk P : P 1 , P 2 , … , P k 中，对于任意 1≤s≠t≤k 1 ≤ s ≠ t ≤ k 都有 Ps≠Pt P s ≠ P t ，那么称路径为简单路径。

Input

　　输入文件的第一行包含两个整数 N N 和 MM ，分别代表图的顶点数和边数。接下来 M M 行，每行包含四个整数 uu 、 v v 、 aa 、 b b 代表一条顶点 uu 和 v v 之间、权值为 2a×3b2a×3b 的边。接下来一行包含一个整数 q q ，代表询问数。接下来 qq 行，每行包含四个整数 u u 、 vv 、 a a 和 bb ，代表一次询问。询问内容请参见问题描述。

　　 1≤n,q≤50000,1≤m≤100000,0≤a,b≤109 1 ≤ n , q ≤ 50000 , 1 ≤ m ≤ 100000 , 0 ≤ a , b ≤ 10 9

Output

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

Sample Input

4 5

1 2 1 3

1 3 1 2

1 4 2 1

2 4 3 2

3 4 2 2

5

1 4 3 3

4 2 2 3

1 3 2 2

2 3 2 2

1 3 4 4

Sample Output

Yes

Yes

Yes

No

No

Solution

题意就是一个图，每条边上有 2 2 个权值 a,ba,b ，每次询问是否有一条 u u 到 vv 的路径（不一定是简单路径），使得路径上的 a a 的最大值和 bb 的最大值恰好等于一个给定的值。

考虑一个暴力的 O((n+m)q) O ( ( n + m ) q ) 算法：

维护一个带权并查集，维护每个连通块的 a a 最大值和 bb 最大值。

对于一个询问 (u,v,A,B) ( u , v , A , B ) ，初始化并查集，并将所有满足 a≤A,b≤B a ≤ A , b ≤ B 的边加入，最后询问 u u 和 vv 是否连通，以及连通块的最大值是否为 A,B A , B 。

考虑使用分块优化。

先将所有的边按照 a a 从小到大排序，分成 m−−√m 块，然后在每一块内按照 b b 排序。

那么对于一个询问，满足条件的边一定是这样分布的（红色部分）：

即合法的边分布在前 kk 块，前 k−1 k − 1 块中合法的边在块内是一个前缀，在第 k k 块中是零散的。

因此，可以把询问按照 kk 进行分组，对每组询问分类处理。

假设现在处理到第 k k 组询问，则将询问按照 BB 从小到大排序。

按照 B B 从小到大排序之后，对于前 k−1k−1 块中选出的边，选到的右边界是递增的，因此用 k−1 k − 1 个指针维护前 k−1 k − 1 块取到的右边界即可。

第 k k 块是零散的，暴力加边。但由于不同询问中第 kk 块内选出的边不同，因此要写一个可持久化支持撤回上一次操作的并查集。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res; 
}
const int N =  + , M =  + , L =  + , Sqrt = ;
int n, m, q, S, fa[N], max2[N], max3[N], QAQ, QWQ, l[Sqrt], r[Sqrt], cnt,
pos[Sqrt], tot, que[M], mina[Sqrt];
bool vis[M], ans[M];
struct cyx {int t, u, f, u2, u3, f2, f3;} o[L];
struct pyz {int u, v, a, b, id;} e[M], c[M];
inline bool comp1(const pyz &x, const pyz &y) {return x.a < y.a;}
inline bool comp2(const pyz &x, const pyz &y) {return x.b < y.b;}
inline int cx(const int &x, const bool &op) {
    if (!op) {int y = x; while (fa[y] != y) y = fa[y]; return y;}
    if (fa[x] != x) o[++QAQ] = (cyx) {QWQ, x, fa[x], -, -, -, -}
        , fa[x] = cx(fa[x], ); return fa[x];
}
inline void zm(const int &x, const int &y, const int &a, const int &b) {
    QWQ++; int ix = cx(x, ), iy = cx(y, );
    if (ix != iy) o[++QAQ] = (cyx) {QWQ, iy, ix, max2[iy], max3[iy],
        max2[ix], max3[ix]}, fa[iy] = ix, max2[ix] =
        max(max(max2[ix], max2[iy]), a), max3[ix] = max(max(max3[ix],
        max3[iy]), b), max2[iy] = max3[iy] = -;
    else o[++QAQ] = (cyx) {QWQ, ix, -, max2[ix], max3[ix], -, -},
        max2[ix] = max(max2[ix], a), max3[ix] = max(max3[ix], b);
}
inline void backto(const int &t) {
    while (o[QAQ].t > t) {
        if (o[QAQ].f == -) max2[o[QAQ].u] = o[QAQ].u2,
            max3[o[QAQ].u] = o[QAQ].u3;
        else {
            fa[o[QAQ].u] = o[QAQ].u2 == - ? o[QAQ].f : o[QAQ].u;
            if (o[QAQ].u2 != -) {
                max2[o[QAQ].u] = o[QAQ].u2; max3[o[QAQ].u] = o[QAQ].u3;
                max2[o[QAQ].f] = o[QAQ].f2; max3[o[QAQ].f] = o[QAQ].f3;
            }
        }
        QAQ--;
    }
    QWQ = t;
}
int main() {
    int i, j, k; n = read(); m = read();
    For (i, , m) e[i].u = read(), e[i].v = read(),
        e[i].a = read(), e[i].b = read();
    q = read(); For (i, , q) c[i].u = read(), c[i].v = read(),
        c[i].a = read(), c[i].b = read(), c[i].id = i; S = sqrt(m);
    sort(e + , e + m + , comp1);
    for (i = ; i <= m; i += S) l[++cnt] = i, r[cnt] = min(m, i + S - ),
        mina[cnt] = e[l[cnt]].a; For (i, , cnt)
        sort(e + l[i], e + r[i] + , comp2); sort(c + , c + q + , comp2);
    For (i, , cnt) {
        For (j, , n) fa[j] = j, max2[j] = max3[j] = -; QAQ = QWQ = tot = ;
        For (j, , i - ) pos[j] = l[j]; For (j, , q)
            if (!vis[j] && (i == cnt || mina[i + ] > c[j].a))
                vis[que[++tot] = j] = ;
        For (j, , tot) {
            For (k, , i - ) while (pos[k] <= r[k] && e[pos[k]].b <= c[que[j]].b)
                zm(e[pos[k]].u, e[pos[k]].v, e[pos[k]].a, e[pos[k]].b), pos[k]++;
            int tmp = QWQ; For (k, l[i], r[i])
                if (e[k].a <= c[que[j]].a && e[k].b <= c[que[j]].b)
                    zm(e[k].u, e[k].v, e[k].a, e[k].b);
            int x = cx(c[que[j]].u, ), y = cx(c[que[j]].v, );
            ans[c[que[j]].id] = x == y && max2[x] == c[que[j]].a
                && max3[y] == c[que[j]].b; backto(tmp);
        }
    }
    For (i, , q) puts(ans[i] ? "Yes" : "No");
    return ;
}