自动搬运

查看原文

来自洛谷，原作者为

	Invisible_H **

搬运于2025-08-24 23:16:34，当前版本为作者最后更新于2025-05-22 16:32:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1

前置知识：最小生成树。

先进行一个转化：

每次花费 $\gcd_{i=l + 1}^{r} B_i$ 的代价，可以连 $(l,r)$ 这一条边。

然后我们需要求 $0∼n$ 的最小生成树。

代码很好写啊就建完全图跑最小生成树，记得清空 $fa$ 数组，时间复杂度 $O(q n ^2 \log n)$。

#include <bits/stdc++.h>
#define int long long

constexpr int maxn = 1e6 + 7;
int B[maxn];
struct node{
	int u, v, w;
}G[maxn];
int fa[maxn], n, q;
inline int find(int u){
	if(u != fa[u]){
		fa[u] = find(fa[u]);
	}
	return fa[u];
}
inline bool cmp(node a, node b){
	return a.w < b.w; 
}
int32_t main(){
	std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false);
	std::cin >> n >> q;
	for(int i = 1; i <= n; i++){
		std::cin >> B[i];
	}
	for(int i = 0; i <= n; i++){
		fa[i] = i;
	}
	int m = 0;
	int k, val;
	for(int i = 0; i <= n; i++){
		int g = B[i + 1];
		for(int j = i + 1; j <= n; j++){
			g = std::__gcd(g, B[j]);
			G[++m].u = i;
			G[m].v = j;
			G[m].w = g;
			
		}
	}
	int ans = 0;
	std::sort(G + 1, G + m + 1, cmp);
	int cnt = 0;
	for(int i = 1; i <= m; i++){
		int fu = find(G[i].u), fv = find(G[i].v);
		if(fu == fv) continue;
		ans += G[i].w;
		fa[fv] = fu;
		cnt++;
		if(cnt == n) break;
	}
	std::cout << ans << '\n';
	while(q--){
		for(int i = 0; i <= n; i++){
			fa[i] = i;
		}
		int m = 0;
		int k, val;
		std::cin >> k >> val;
		B[k] = val;
		for(int i = 0; i <= n; i++){
			int g = B[i + 1];
			for(int j = i + 1; j <= n; j++){
				g = std::__gcd(g, B[j]);
				G[++m].u = i;
				G[m].v = j;
				G[m].w = g;
				
			}
		}
		int ans = 0;
		std::sort(G + 1, G + m + 1, cmp);
		int cnt = 0;
		for(int i = 1; i <= m; i++){
			int fu = find(G[i].u), fv = find(G[i].v);
			if(fu == fv) continue;
			ans += G[i].w;
			fa[fv] = fu;
			cnt++;
			if(cnt == n) break;
		}
		std::cout << ans << '\n';
	}
	return 0;
}

Part 2

考虑优化。

前置知识：最小生成树。

根据 Kruskal 的思想，$(0,n)$ 这条边一定会被选。

然后根据 Prim 的思想，对于某个点，我们需要找到其最短的出边。

而显然对于 $i$，它最短的出边为 $(i,0)$ 或者 $(i,n)$。边权为 $L_i=\gcd_{j=1}^{i} B_j$ 和 $R_i=\gcd_{j=i+1}^{n} B_j$。

然后你只需要建 $0$ 到所有点的边和 $n$ 到所有点的边就好了，时间复杂度 $O(q n \log n)$。

#include <bits/stdc++.h>
#define int long long

constexpr int maxn = 1e6 + 7;
int B[maxn], m;
struct node{
	int u, v, w;
}G[maxn];
int fa[maxn], n, q;
inline int find(int u){
	if(u != fa[u]){
		fa[u] = find(fa[u]);
	}
	return fa[u];
}
inline bool cmp(node a, node b){
	return a.w < b.w; 
}
int32_t main(){
	std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false);
	std::cin >> n >> q;
	for(int i = 1; i <= n; i++){
		std::cin >> B[i];
	}
	for(int i = 0; i <= n; i++){
		fa[i] = i;
	}
	int m = 0;
	int k, val;
	int g = 0;
	for(int i = 1; i <= n; i++){
		g = std::__gcd(g ,B[i]);
		G[++m].u = 0;
		G[m].v = i;
		G[m].w = g;
	}
	g = 0;
	for(int i = n; i >= 1; i--){
		g = std::__gcd(g ,B[i]);
		G[++m].u = i - 1;
		G[m].v = n;
		G[m].w = g;
	}
	int ans = 0;
	std::sort(G + 1, G + m + 1, cmp);
	int cnt = 0;
	for(int i = 1; i <= m; i++){
		int fu = find(G[i].u), fv = find(G[i].v);
		if(fu == fv) continue;
		ans += G[i].w;
		fa[fv] = fu;
		cnt++;
		if(cnt == n) break;
	}
	std::cout << ans << '\n';
	while(q--){
		for(int i = 0; i <= n; i++){
			fa[i] = i;
		}
		int m = 0;
		int k, val;
		std::cin >> k >> val;
		B[k] = val;
		int g = 0;
		for(int i = 1; i <= n; i++){
			g = std::__gcd(g ,B[i]);
			G[++m].u = 0;
			G[m].v = i;
			G[m].w = g;
		}
		g = 0;
		for(int i = n; i >= 1; i--){
			g = std::__gcd(g ,B[i]);
			G[++m].u = i - 1;
			G[m].v = n;
			G[m].w = g;
		}
		int ans = 0;
		std::sort(G + 1, G + m + 1, cmp);
		int cnt = 0;
		for(int i = 1; i <= m; i++){
			int fu = find(G[i].u), fv = find(G[i].v);
			if(fu == fv) continue;
			ans += G[i].w;
			fa[fv] = fu;
			cnt++;
			if(cnt == n) break;
		}
		std::cout << ans << '\n';
	}
	return 0;
}

Part 3

考虑继续优化。

前置知识：线段树二分。

显然 $L_i$ 是单调不增，$R_i$ 是单调不减的。

所以一定存在一个 $p \in [0,n),\forall i\in[0,p],R_i \leq Li,\forall i \in (p,n),Li \leq Ri$。

我们可以用线段树维护每个区间 $[l,r]$ 的 $\gcd_{l+1}^{r} B_i$，然后在线段树上二分求出 $p$。

而题目所给的修改可以直接单点修改。

剩下的就是求 $\sum_{i=0}^{p} R_i + \sum_{i=p+1}^{n-1} L_i$。

考虑到 $L_i$ 以及 $R_i$ 的取值个数是 $\log n$ 级别的，我们可以在线段树上暴力找出这些取值以及其对应的区间，时间复杂度 $O(q \log^2 n)$。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
int SGT[400007];
void build(int p, int l, int r) {
    if (l == r)
        return (void)(std::cin >> SGT[p]);

    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r), SGT[p] = std::__gcd(SGT[p << 1], SGT[p << 1 | 1]);
}
void update(int p, int l, int r, int x, int v) {
    if (l == r)
        return (void)(SGT[p] = v);

    x <= mid ? update(p << 1, l, mid, x, v) : update(p << 1 | 1, mid + 1, r, x, v);
    SGT[p] = std::__gcd(SGT[p << 1], SGT[p << 1 | 1]);
}
int Find(int p, int l, int r, int a, int b) {
    if (l == r)
        return l;

    int x = std::__gcd(a, SGT[p << 1]), y = std::__gcd(b, SGT[p << 1 | 1]);
    return x <= y ? Find(p << 1, l, mid, a, y) : Find(p << 1 | 1, mid + 1, r, x, b);
}
int cal1(int p, int l, int r, int x, int v) {
    if (l == r)
        return std::__gcd(SGT[p], v);

    int a = std::__gcd(SGT[p << 1 | 1], v), b = std::__gcd(SGT[p << 1], a);
    return x <= mid ? cal1(p << 1, l, mid, x, a) : (a == b ? 1ll * (mid - l + 1) * a : cal1(p << 1, l, mid, x, a)) + cal1(p << 1 | 1, mid + 1, r, x, v);
}
int cal2(int p, int l, int r, int x, int v) {
    if (l == r)
        return std::__gcd(SGT[p], v);

    int a = std::__gcd(SGT[p << 1], v), b = std::__gcd(SGT[p << 1 | 1], a);
    return x > mid ? cal2(p << 1 | 1, mid + 1, r, x, a) : (a == b ? 1ll * (r - mid) * a : cal2(p << 1 | 1, mid + 1, r, x, a)) + cal2(p << 1, l, mid, x, v);
}
int32_t main() {
    int n, Q;
	std::cin >> n >> Q; 
    build(1, 1, n);
	int p = Find(1, 1, n, 0, 0);
	std::cout << (cal1(1, 1, n, p, 0) + cal2(1, 1, n, p, 0) - SGT[1]) << '\n';
    for (int p, v; Q; --Q) std::cin >> p >> v, update(1, 1, n, p, v), p = Find(1, 1, n, 0, 0), std::cout << (cal1(1, 1, n, p, 0) + cal2(1, 1, n, p, 0) - SGT[1]) << '\n';

    return 0;
}