DDOSvoid's Blog

Luogu P3247 [HNOI2016]最小公倍数

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P3247

简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，第 $i$ 条边的边权为 $(a_i,b_i)$，现在有 $q$ 次询问，每次询问给定 $u,v,a,b$，问是否存在一条从 $u$ 到 $v$ 的路径满足路径上所有边的 $a_i\le a,b_i\le b$ 且满足 $max a_i=a,max b_i=b$

$n,q\le 5\times 10^4,m\le 10^5$

Solution

我们考虑首先将边按照 $a$ 排序后分块，那么每个询问所对应的边都是一个前缀，这个前缀包含了一些整块和一个散块，我们将这个询问放进这个散块中，同时每个散块中的边按照 $b$ 排序

然后我们直接暴力，我们枚举块，然后将这个块之前所有块内的边按照 $b$ 排序，然后我们枚举当前块内的询问，询问已经按照 $b$ 排好序，那么对于前面所有整块的内的边和询问是一个双指针的过程，而散块内的边我们暴力加入即可

维护边使用带撤销并查集即可，取块大小为 $\sqrt {n\log n}$ 可以得到时间复杂度为 $O(n\sqrt {n\log n})$

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define maxn 50010
#define maxm 100010
#define sqtn 400
#define INF 1000000000
using namespace std;

int n, m, q;

struct node {
    int u, v, a, b, id;
} e[maxm], Q[maxn];
inline bool cmpa(const node &u, const node &v) { return u.a < v.a; }
inline bool cmpb(const node &u, const node &v) { return u.b < v.b; } 

int l[sqtn], r[sqtn], blo, num;
int la[sqtn], ra[sqtn]; vector<int> A[sqtn];
void init_blo(int n) {
    blo = sqrt(n * 15); num = (n + blo - 1) / blo;
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n; sort(e + 1, e + n + 1, cmpa); 
    for (int i = 1; i <= num; ++i) {
        la[i] = e[l[i]].a, ra[i] = e[r[i]].a;
    }
}

struct Node {
    int x, y, deep, a, b;
} st[maxm]; int top;

int fa[maxn], dep[maxn], ma[maxn], mb[maxn]; 
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, dep[i] = 1, ma[i] = mb[i] = -1; top = 0; }

int find(int x) { return fa[x] == x ? x : find(fa[x]); }

inline void merge(int x, int y, int a, int b) {
    x = find(x); y = find(y); 
    if (dep[x] > dep[y]) swap(x, y);
    st[++top] = {x, y, dep[y], ma[y], mb[y]};
    ma[y] = max(ma[y], a); mb[y] = max(mb[y], b); 
    if (x == y) return ;
    fa[x] = y; if (dep[x] == dep[y]) ++dep[y];
    ma[y] = max(ma[y], ma[x]); mb[y] = max(mb[y], mb[x]); 
}

void undo() {
    while (top) {
        int x = st[top].x, y = st[top].y, deep = st[top].deep, a = st[top].a, b = st[top].b; 
        fa[x] = x; dep[y] = deep; ma[y] = a; mb[y] = b;
        --top;
    }
}

bool ans[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].a >> e[i].b;
    cin >> q; 
    for (int i = 1; i <= q; ++i) cin >> Q[i].u >> Q[i].v >> Q[i].a >> Q[i].b, Q[i].id = i;
    
    init_blo(m);
    
    sort(Q + 1, Q + q + 1, cmpa);
    for (int i = 1, j = 1; i <= q; ++i) {
        while (j <= num && ra[j] <= Q[i].a) ++j;
        A[j].push_back(i); 
    }
    for (int i = 1; i <= num + 1; ++i) 
        sort(A[i].begin(), A[i].end(), [](const int &u, const int &v) {return Q[u].b < Q[v].b;});
    
    l[num + 1] = m + 1; r[num + 1] = 0; 
    for (int i = 1; i <= num + 1; ++i) {
        sort(e + 1, e + l[i], cmpb);
        int j = 1; init_fa(n); 
        for (auto k : A[i]) {
            while (j < l[i] && e[j].b <= Q[k].b)
                merge(e[j].u, e[j].v, e[j].a, e[j].b), ++j;
            top = 0; 
            for (int j = l[i]; j <= r[i]; ++j)
                if (e[j].a <= Q[k].a && e[j].b <= Q[k].b)
                    merge(e[j].u, e[j].v, e[j].a, e[j].b);
            int u = find(Q[k].u), v = find(Q[k].v);
            if (u == v && ma[u] == Q[k].a && mb[u] == Q[k].b)
                ans[Q[k].id] = true;
            else ans[Q[k].id] = false;
            undo();
        }
    }
    
    for (int i = 1; i <= q; ++i) cout << (ans[i] ? "Yes" : "No") << "\n";
    return 0;
}