自动搬运

查看原文

来自洛谷，原作者为

	缪凌锴_Mathew 希↑望→计↓划↑可→以↑成↓功↓ | 离错真机

搬运于2025-08-24 22:50:04，当前版本为作者最后更新于2023-09-13 13:00:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

首先，如果只求最大值之和就比较简单。

对于每一个点 $x$，求出最小的 $l$，最大的 $r$，使得：

• $a_{l},a_{l+1},\dots,a_{x-1} <a_x$

• $a_{x+1},a_{x+2},\dots,a_r \le a_x$

例如下面这个例子:

24 18 20 14 15 30

对于 $x=3,a_x=20$ 来说 $l=2,r=5$。

$l$ 再减小，则 $24>20$，$r$ 再增大，则 $30>20$。

所有 $l \le i \le x \le j \le r$ 的区间 $[i,j]$ 的最大值为 $a_x$。

此时对答案的贡献为 $a_x \times \sum_{l \le i \le x \le j \le r} G(i,j)$。

快速求这个 $l,r$，考虑倍增，预处理出每个点向前和向后 $2^k$ 个数的最大值，倍增跳 $l,r$ 到边界。

为什么第一个条件是 $<x$ 而不是 $\le x$ 呢？

序列中有相等的数会使得区间被重复计算。

我们向右扩到 $n$，向左扩不超过上一个一样的数，就可以避免使得区间被重复计算。

用 map 维护就能求出上一个一样的数了。

现在要求所有 $l \le i \le x \le j \le r$ 的区间 $[i,j]$ 的区间 gcd 的和。

观察这个样例从第一个数开始的前缀 gcd：

72 36 48 12 24 18 24 36 66 44 26 34 17 19 51

所有前缀 gcd，若有变化，则变化前的 $lstgcd$ 为变化后的 $nxtgcd$ 的倍数。$nxtgcd \le \dfrac{lstgcd}{2}$，因此 gcd 最多有 $\log V$ 种。

得到结论，$x \le p \le r$ 的区间 $[x,p]$ 的 gcd 只有 $\log V$ 种。

同理 $l \le p \le x$ 的区间 $[p,x]$ 的 gcd 只有 $\log V$ 种。

我们只需把两边的这 $\log V$ 种 gcd 求出来，直接暴力 $O(log^{2} V)$ 枚举求答案。

同样，倍增求值，预处理出每个点向前和向后 $2^k$ 个数的 gcd ，每个 gcd 值倍增跳到边界。

复杂度看似还有一个 gcd 的 $O(\log V)$，实际上我们做区间 $[x,i]$ 的 gcd 时可以利用上一次的 gcd ，辗转相除一共 $O(\log V)$ 次，均摊下来每次 gcd 的复杂度为 $O(1)$。

总复杂度 $O(n \log^{2} V)$。

代码

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
const int MAXM=25;//log n
const int M=20;
const int MAXK=35;//log V
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int n,ans=0;
int a[MAXN];
int maxl[MAXN][MAXM],maxr[MAXN][MAXM];//i向左、向右2^k个数的最大值
int gcdl[MAXN][MAXM],gcdr[MAXN][MAXM];//i向左、向右2^k个数的gcd
map <int,int> mp;
struct node{//每一个最大公因数的范围，数值
    int ql,qr,val;
}L[MAXK],R[MAXK];
int cntl,cntr;//左。右的最大公因数的数值个数（<logV）
void work(int x){
    int l=x,r=x;
    int lim=mp[a[x]];//上一个一样的数（没有则为0）
    for(int i=M;i>=0;i--)//倍增跳l和r
    {
        if(l-(1<<i)>lim&&maxl[l-1][i]<=a[x]){
            l-=(1<<i);
        }
        if(r+(1<<i)<=n&&maxr[r+1][i]<=a[x]){
            r+=(1<<i);
        }
    }
    cntl=0;
    cntr=0;
    int Gcd=a[x],p=x;//当前最大公因数的数值，当前位置
    while(1)
    {
        int lst=p;
        for(int i=M;i>=0;i--)
        {
            if(p-(1<<i)>=l&&gcdl[p-1][i]%Gcd==0){
                p-=(1<<i);
            }
        }
        cntl++;
        L[cntl]=(node){p,lst,Gcd};
        if(p==l){
            break;
        }
        p--;
        Gcd=gcd(Gcd,a[p]);
    }
    Gcd=a[x];
    p=x;
    while(1)
    {
        int lst=p;
        for(int i=M;i>=0;i--)
        {
            if(p+(1<<i)<=r&&gcdr[p+1][i]%Gcd==0){
                p+=(1<<i);
            }
        }
        cntr++;
        R[cntr]=(node){lst,p,Gcd};
        if(p==r){
            break;
        }
        p++;
        Gcd=gcd(Gcd,a[p]);
    }
    int res=0;
    //暴力统计答案
    for(int i=1;i<=cntl;i++)
    {
        int lst=L[i].val;//优化gcd
        for(int j=1;j<=cntr;j++)
        {
            int lenl=L[i].qr-L[i].ql+1;
            int lenr=R[j].qr-R[j].ql+1;
            res+=1ll*lenl*lenr%mod*gcd(lst,R[j].val)%mod;
            res%=mod;
        }
    }
    ans+=1ll*res*a[x]%mod;
    ans%=mod;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        maxl[i][0]=a[i];
        maxr[i][0]=a[i];
        gcdl[i][0]=a[i];
        gcdr[i][0]=a[i];
    }
    for(int i=1;i<=M;i++)//预处理
    {
        int len=(1<<(i-1));
        for(int j=1;j<=n;j++)
        {
            maxl[j][i]=maxl[j][i-1];
            maxr[j][i]=maxr[j][i-1];
            gcdl[j][i]=gcdl[j][i-1];
            gcdr[j][i]=gcdr[j][i-1];
        }
        for(int j=1;j+len<=n;j++)
        {
            maxr[j][i]=max(maxr[j][i],maxr[j+len][i-1]);
            gcdr[j][i]=gcd(gcdr[j][i],gcdr[j+len][i-1]);
        }
        for(int j=len+1;j<=n;j++)
        {
            maxl[j][i]=max(maxl[j][i],maxl[j-len][i-1]);
            gcdl[j][i]=gcd(gcdl[j][i],gcdl[j-len][i-1]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        work(i);
        mp[a[i]]=i;
    }
    printf("%d\n",ans);
    return 0;
}

update 2023.10.8 改正一个错误，感谢 @Sunny郭 指出。

update 2023.10.25 改正一个复杂度分析的错误，感谢 @VioletIsMyLove 指出。