题意
给长度为 \(n\) 的数组 \(a\),求长度不小于 \(k\) 的区间 \([l,r]\) 使得 \(\gcd_{i = l}^r a_i \times \sum_{i = l}^r a_i\) 最大,输出这个最大值。
\(1\le k\le n\le 10^6,1\le a_i \le 10^6\qquad \text{2.5s 512MB}\)
题解
考虑分治(这是套路,想不到只能说做题少别打我)。
递归求解区间 \([l,r]\),若 \(r - l + 1\le k\) 则直接返回,\(l = r\) 且 \(k = 1\) 就用 \(a_i^2\) 更新答案。
引入一个结论,当一段区间 \(\gcd\) 相同时,肯定是选的数越多,答案越大。
对于一般情况,我们将 \([l,r]\) 分为 \([l,mid],(mid,r]\)。由上述结论可得,我们可以维护区间中每一段 \(\gcd\) 相同的区间,分别记录 \([l,mid]\) 和 \((mid,r]\) 的 \(\gcd\) 变化的位置,这样的位置至多只有 \(\log V\) 个。具体地,对于 \([l,mid]\) 维护后缀 \(\gcd\) 和后缀 \(\gcd\) 变化位置,同理 \((mid,r]\) 维护前缀 \(\gcd\) 和前缀 \(\gcd\) 变化位置(注意 \(l,r\) 同样也算作变化位置),存在 vector
里面,然后枚举区间 \([l,mid]\) 的变化位置 \(L\),区间 \((mid,r]\) 的变化位置 \(R\),若 \(R - L + 1 \ge k\),那么用 \(\gcd(suf_L,pre_R)\times(s_R - s_{L - 1})\) 更新答案。
枚举时间复杂度 \(\mathcal{O}(\log^2V)\),所以最终复杂度 \(\mathcal{O}(n\log n\log^2 V)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,k,a[N];
#define ll long long
ll s[N],ans;
int pre[N],suf[N];
vector<int> P,S;
void solve(int l,int r){
if (r - l + 1 < k) return ;
if (l == r && k == 1){
ans = max(ans,1ll * a[l] * a[l]);
return ;
}
int mid = (l + r) >> 1;
solve(l,mid), solve(mid + 1,r);
for (int i = mid;i >= l;i--){
suf[i] = __gcd(suf[i + 1],a[i]);
if (i == mid) suf[i] = a[i];
else if (suf[i] != suf[i + 1]) S.push_back(i + 1);
}
for (int i = mid + 1;i <= r;i++){
pre[i] = __gcd(pre[i - 1],a[i]);
if (i == mid + 1) pre[i] = a[i];
else if (pre[i] != pre[i - 1]) P.push_back(i - 1);
}
P.push_back(r), S.push_back(l);
for (int L : S)
for (int R : P)
if (R - L + 1 >= k)
ans = max(ans,1ll * __gcd(suf[L],pre[R]) * (s[R] - s[L - 1]));
P.clear(), S.clear();
}
int main(){
scanf("%d%d",&n,&k);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]), s[i] = s[i - 1] + a[i];
solve(1,n);
printf("%lld",ans);
return 0;
}
标签:COCI2022,P9032,le,gcd,suf,int,mid,Neboderi,ans
From: https://www.cnblogs.com/y1wei/p/-/solution_Luogu_P9032