算法

赛时也是想到了大部分吧, 实现上还是有问题

这里给出一种判断自己是否想出了正解的办法: 如果问题足够复杂, 解法足够简单, 那么是错的, 因为我不是天赋哥

转化题意

对于序列 \(s\) , 找出一段区间 \([L, R]\) , 使得区间长度至少为 \(k\) 的前提下, 令所有数的 \(\gcd\) 为 \(g\) , 求

题意其实给的很清楚了, 不太需要转化

区间长是 \(10^6\) 级别的, 不好处理

暴力的做法是, 考虑对于一个固定的 \(R\) , 我们向前走, 记录 \(\sum\) 值和 \(\gcd\) , 可以做到 \(\mathcal{O} (n ^ 2)\) 的时间复杂度, \(30 \rm{pts}\)

容易的, 发现 \(\gcd\) 的特殊 \(\rm{trick}\) , 对于固定的右端点, 左侧 \(\gcd\) 的值变化的次数最多是 \(\log V\) 级别的, 考虑利用这个结论

对于每次右端点的拓张, 假设当前右端点为 \(i\) , 我们都可以利用右端点为 \(i - 1\) 的计算信息, 不需要再去计算 \(\gcd\) 的分段

具体的, 维护链表存储之前每个分割点, 每次拓张到 \(i\) 时, 考虑更新链表中的区间 \(\gcd\) , 然后将链表中区间 \(\gcd\) 相同的部分合并, 总之, 链表中的元素最多只有 \(\log V\) 个

显然的, 时间复杂度为 \(\mathcal{O} ({n \log^2 V})\) , 其中 \(V\) 为值域

也是基本上全都想到了, 但是试图使用优秀算法

代码

维护链表即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N], nxt[N], val[N], num[N], head, cnt;
long long ans, sum[N];
signed main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
    for (int r = 1; r <= n; r++)
    {
        for (int pre = head; pre; pre = nxt[pre])
            val[pre] = __gcd(val[pre], a[r]);
        nxt[++cnt] = head, head = cnt, val[cnt] = a[r], num[cnt] = r;
        for (int pre = head; pre; pre = nxt[pre])
        {
            while (val[pre] == val[nxt[pre]])
                num[pre] = num[nxt[pre]], nxt[pre] = nxt[nxt[pre]];
            if (r - num[pre] + 1 >= k)
                ans = max(ans, (sum[r] - sum[num[pre] - 1]) * val[pre]);
        }
    }
    printf("%lld", ans);
    return 0;
}

总结

对问题大概需要的最少复杂度要有意识, 当不好解决时, 考虑加上一个 \(\log\) 再处理

注意链表合并这中问题, 大部分时候仅仅是 \(\mathcal{O} (L)\) 的, 其中 \(L\) 为链长