OI

BZOJ 4537: [Hnoi2016]最小公倍数

Description

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

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

注意：路径可以不是简单路径。下面是一些可能有用的定义：最小公倍数：K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。

路径：路径P:P1,P2,…,Pk是顶点序列，满足对于任意1<=i<k，节点Pi和Pi+1之间都有边相连。简单路径：如果路径P:P1,P2,…,Pk中，对于任意1<=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。

Input

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

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

HINT

1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

Solution

分块+并查集。

首先想暴力怎么做？

对于每个询问我们把所有a<=query_a, b<=query_b的边都扔到并查集里维护一下就可以回答了。

标算采用了分块加速这个过程：

我们按照a的大小对边排序，分为若干块，同样按a的大小对询问排序。

然后从小到大找第一个没有回答的询问，定位到他所在的块，把这块之前的边都取出来按照b排个序，然后找到此次询问可以回答的其他询问，把这些询问拿出来也按照b排个序，然后对于这些询问：

  • Two-Pointer扫描该块之前的所有边
  • 暴力处理该块内的边

然后判断这个询问所在的联通快最大的a，b就可以了。

Source

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int block_siz = 316;
const int block_cnt = maxn / block_siz + 10;
inline int getint() {
    register int r = 0; register bool b = true; register char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
    return b ? r : -r;
}
struct edge_t { int u, v, a, b; } e[maxn], ee[maxn];
struct query_t { int u, v, a, b, id; } q[maxn];
struct modify_t { int id, fa, siz, mxa, mxb; } sta[maxn];
int n, m, Q, mxa[maxn], mxb[maxn], siz[maxn], fa[maxn], tail, mx[block_cnt + 9], L[block_cnt + 9], R[block_cnt + 9], ptr, ppp;
bool ans[maxn];
inline bool cmpea(const edge_t &x, const edge_t &y) { return x.a < y.a; }
inline bool cmpeb(const edge_t &x, const edge_t &y) { return x.b < y.b; }
inline bool cmpqa(const query_t &x, const query_t &y) { return x.a < y.a; }
inline bool cmpqb(const query_t &x, const query_t &y) { return x.b < y.b; }
inline int Find(int x) { while (fa[x] != x) x = fa[x]; return x; }
inline void Mer(int u, int v, int a, int b, bool o) {
    int x = Find(u), y = Find(v);
    if (x == y) {
        if (a > mxa[x] || b > mxb[x]) {
            if (o) sta[++tail] = modify_t{x, fa[x], siz[x], mxa[x], mxb[x]};
            mxa[x] = max(mxa[x], a);
            mxb[x] = max(mxb[x], b);
        }
    }
    else {
        if (siz[x] < siz[y]) swap(x, y);
        if (o) {
            sta[++tail] = modify_t{x, fa[x], siz[x], mxa[x], mxb[x]};
            sta[++tail] = modify_t{y, fa[y], siz[y], mxa[y], mxb[y]};
        }
        fa[y] = x;
        siz[x] += siz[y];
        mxa[x] = max(mxa[x], max(a, mxa[y]));
        mxb[x] = max(mxb[x], max(b, mxb[y]));
    }
}
inline void Undo(int i) {
    int x = sta[i].id;
    fa[x] = sta[i].fa;
    siz[x] = sta[i].siz;
    mxa[x] = sta[i].mxa;
    mxb[x] = sta[i].mxb;
}
inline bool Check(int u, int v, int a, int b) {
    int x = Find(u), y = Find(v);
    if (x != y) return false;
    if (mxa[x] < a || mxb[x] < b) return false;
    return true;
}
inline void Init() {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        siz[i] = 1;
        mxa[i] = -1;
        mxb[i] = -1;
    }
}
int main() {
    n = getint(); m = getint();
    for (int i = 1; i <= m; ++i) {
        e[i].u = getint();
        e[i].v = getint();
        e[i].a = getint();
        e[i].b = getint();
    }
    sort(e + 1, e + m + 1, cmpea);
    int cnt = (m + block_siz - 1) / block_siz;
    R[0] = 1;
    for (int i = 1; i <= cnt; ++i) {
        L[i] = R[i-1];
        R[i] = L[i] + block_siz;
        if (R[i] > m + 1) R[i] = m + 1;
        mx[i] = e[R[i] - 1].a;
    }
    Q = getint();
    for (int i = 1; i <= Q; ++i) {
        q[i].u = getint();
        q[i].v = getint();
        q[i].a = getint();
        q[i].b = getint();
        q[i].id = i;
    }
    sort(q + 1, q + Q + 1, cmpqa);
    ppp = 1;
    ptr = 1;
    Init();
    int i = 1;
    L[cnt + 1] = R[cnt + 1] = m + 1;
    mx[cnt + 1] = q[Q + 1].a = 2147483647;
    while (i <= Q) {
        while (mx[ptr] <= q[i].a) {
            Init();
            ppp = 1;
            sort(e + L[ptr], e + R[ptr], cmpeb);
            merge(e + 1, e + L[ptr], e + L[ptr], e + R[ptr], ee + 1, cmpeb);
            copy(ee + 1, ee + R[ptr], e + 1);
            ++ptr;
        }
        int ii = i + 1;
        while (mx[ptr] > q[ii].a) ++ii;
        sort(q + i, q + ii, cmpqb);
        while (i < ii) {
            while (ppp < L[ptr] && e[ppp].b <= q[i].b) {
                Mer(e[ppp].u, e[ppp].v, e[ppp].a, e[ppp].b, false);
                ++ppp;
            }
            for (int j = L[ptr]; j < R[ptr]; ++j)
                if (e[j].a <= q[i].a && e[j].b <= q[i].b)
                    Mer(e[j].u, e[j].v, e[j].a, e[j].b, true);
            ans[q[i].id] = Check(q[i].u, q[i].v, q[i].a, q[i].b);
            while (tail) Undo(tail--);
            ++i;
        }
    }
    for (int i = 1; i <= Q; ++i) {
        if (ans[i]) puts("Yes");
        else puts("No");
    }
}