连边
题面
给定一张初始 \(n\) 个点，没有边的图。
给定 \(m\) 表示有 \(m\) 个时刻，第 \(i\) 个时刻会将 \(gcd(a,b) = m - i + 1\) 某些点连起来。
有 \(q\) 个询问，每次询问给定 \(x, y\)，你需要回答 \(x, y\) 最早在什么时刻连通
\(1 \le n,q \le 10^5, 1 \le m \le n\)
题解
这个暴力思路就是直接模拟。
考虑优化，我们可以对原来加的边进行一个等价变形：每个时刻将 \(i\) 和 \(i\) 的倍数连边，边权为 \(i\) ，连通性是一样的。
这样，边数最多只有 \(O(n \log n)\) 。
我们对这些边按照边权从小到大加入到图中，用并查集维护连通性，从而构造出一棵最小生成树。
然后直接倍增查询路径最大边权即为答案。
时间复杂度 \(O(n \log n)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>using namespace std;namespace michaele {const int N = 1e5 + 10, M = N << 1;int n, m, q;int h[N], ver[M], ne[M], e[M], tot;int anc[N], f[N][23], g[N][23], dep[N];void add (int x, int y, int z) {ver[ ++ tot] = y;ne[tot] = h[x];h[x] = tot;e[tot] = z;}int fin (int x) {return x == anc[x] ? x : anc[x] = fin (anc[x]);}void dfs (int x, int fa) {for (int i = h[x]; i; i = ne[i]) {int y = ver[i];if (y == fa) continue;f[y][0] = x;g[y][0] = e[i];dep[y] = dep[x] + 1;dfs (y, x);}}int query (int x, int y) {if (dep[x] < dep[y]) swap (x, y);int res = 1;for (int i = 20; i >= 0; i --) {if (dep[f[x][i]] >= dep[y]) {res = max (res, g[x][i]);x = f[x][i];}}if (x == y) return res;for (int i = 20; i >= 0; i --) {if (f[x][i] != f[y][i]) {res = max ({res, g[x][i], g[y][i]});x = f[x][i];y = f[y][i];}}res = max ({res, g[x][0], g[y][0]});return res;}void solve () {cin >> n >> m >> q;for (int i = 1; i <= n; i ++) anc[i] = i;for (int i = 1; i <= m; i ++) {int k = m - i + 1;for (int j = k * 2; j <= n; j += k) {int x = fin (k), y = fin (j);if (x != y) {anc[x] = y;add (k, j, i);add (j, k, i);}}}dep[1] = 1;dfs (1, 0);for (int j = 1; j <= 19; j ++) {for (int i = 1; i <= n; i ++) {if (!f[i][j - 1]) continue;f[i][j] = f[f[i][j - 1]][j - 1];g[i][j] = max (g[i][j - 1], g[f[i][j - 1]][j - 1]);}}for (int i = 1; i <= q; i ++) {int x, y;cin >> x >> y;if (x == y) {cout << 0 << endl;continue;}cout << query (x, y) << endl;}}
}int main () {ios :: sync_with_stdio (0);cin.tie (0);cout.tie (0);michaele :: solve ();return 0;
}