P9032

Anonymely · 2023-11-08 20:29:27 · 题解

题意：有一个长为 n 的数组 h_i 和一个 k，你可以选择一个长度至少为 k 的区间 [l,r] ，设区间 [l,r] 内所有数的 \gcd 为 g，则这个区间的权值是 g\times \sum^{r}_{i=l} h_i。输出所有合法区间的最大权值，1\le k\le n\le 10^6,1\le h_i\le 10^6。

sol：首先考虑区间 \gcd 的一个经典性质：固定左端点，则对应区间右端点的 \gcd 取值只会变化 \log V 次，其中 V 是值域。证明很简单，每次 \gcd 变化最少会将其除以 2 ，最多除 \log 次就变成 1 了。

从小到大枚举左端点，用 \log 次二分找出这 \log 个 \gcd 变化的位置，用 ST 表 O(\log V) 地求区间 \gcd ，可以做到 O(n\log n\log^2V) ，实现得优秀可以过，但是我们有更好的解法。

正难则反，我们改成从大到小枚举左端点，假设枚举到 i ，不难发现以 i 为左端点 \gcd 变化的位置是可以继承左端点为 i+1 的答案的。具体来说，维护一个链表表示 \gcd 变化的位置，从 i+1 转移到 i 时，先将链表中所有区间 \gcd 的值与 h_i 求个 \gcd ，再将 i 加入链表，最后将链表中相邻两个位置值相同的合并起来。

由于先前的分析，链表中的元素始终不会超过 \log 个，总时间复杂度是 O(n\log n\log V) 。

#include<bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long
#define pii pair <int, int> 

const int N = 1e6 + 5;
int n, k;
int nxt[N], val[N];
ll s[N], ans;

int gcd(int x, int y) {
    if (!y)     return x;
    return gcd(y, x % y);
}

void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        s[i] = s[i - 1] + val[i];
        nxt[i] = i + 1;
    }
    nxt[n + 1] = n + 1;
    for (int l = n; l >= 1; l--) {
        int now = l;
        for(; now != n + 1;){
            val[now] = gcd(val[l], val[now]);
            if(nxt[now] - l >= k) {
                ans = max(ans, val[now] * (s[nxt[now] - 1] - s[l - 1]));
            }
            now = nxt[now];
        }
        now = l;
        for (; now != n + 1;) {
            while(val[now] == val[nxt[now]]) {
                nxt[now] = nxt[nxt[now]];
            }
            now = nxt[now];
        }
    }
    cout << ans << '\n'; 
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    QwQ330AwA;
}

为什么突然写这篇题解呢，熟悉我的人知道我是基本不写 luogu 题解的。所以说是为什么呢？是为什么呢？

2023.11.8