题目链接
咕咕咕
对于求解区间权值 $=value *length$ 的最值问题时，我们通常可以枚举区间左端点，然后高效地找出右端点更新答案。
朴素的想法是枚举右端点 $r\in [l,n]$ 。根据显然的贪心策略，如果右端点在某一区间移动时，$\gcd(a_l,a_{l+1},…,a_r)$ 保持不变，则右端点越大越好。
因此可以用倍增优化右端点的确定。但是在倍增的过程中，需要多次查询区间最大公约数；我们可以用ST表的思路对序列预处理，做到 $O(1)$ 复杂度查询。
但是，如果已经确定左端点 $l$ ，不同的右端点选取会对应许多不同的最大公约数值，那么该算法的复杂度将无法承受。
稍加观察，可以发现当左端点确定时，右端点右移一个单位，原子段的最大公约数要么维持不变；要么变为原最大公约数的一个约数。换言之，当左端点确定时，不同的右端点最多对应 $\log_2n$ 个不同的最大公约数值。算法复杂度得以控制在 $O(n(\log n)^2)$ 。
代码如下：
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int T, N;
ll ans;
ll a[100005];
ll st[100005][18];
int lg[100005];
inline ll query(int l, int r) {
int k = lg[r - l + 1];
return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
lg[1] = 0;
for (register int i = 2; i <= 100000; ++i)
lg[i] = lg[i >> 1] + 1;
scanf("%d", &N);
for (register int i = 1; i <= N; ++i)
scanf("%lld", &st[i][0]);
for (register int j = 1; j <= lg[N]; ++j)
for (register int i = 1; i + (1 << j) - 1 <= N; ++i)
st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
for (register int l = 1; l <= N; ++l) {
int r = l;
while (r <= N) {
ll cur = query(l, r);
for (register int i = lg[N]; i >= 0; --i) {
if (r + (1 << i) <= N && query(l, r + (1 << i)) == cur)
r += (1 << i);
}
ans = max(ans, cur * (r - l + 1));
r += 1;
}
}
printf("%lld", ans);
return 0;
}
|