2020牛客国庆集训派对day1 B

Description

给定一个序列，求其所有子区间的 max 和 gcd 的乘积的和。

Solution

考虑枚举右端点，将右端点不断向右移动，同时维护 f[i] 表示 max(a[i],a[i+1],...,a[r])，维护 g[i] 表示 gcd(a[i],a[i+1],...,a[r])，维护 nxt[i] 表示最大的满足 g[nxt[i]]!=g[i] 的位置

（注意 g[i] 并不需要实时维护，只要保证会用到的点是正确的就可以了）

f[i] 用线段树和单调栈维护（需要支持区间修改和区间求和），g[i] 暴力维护即可

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

#define int long long 
const int N = 1000005;
const int mod = 1e+9+7;

int a[N],f[N],g[N],nxt[N],n,val[N],sta[N],tag[N];

void maintain(int p)
{
    tag[p]%=mod;
    val[p]%=mod;
}

void pushup(int p)
{
    val[p]=(val[p*2]+val[p*2+1])%mod;
}

void pushdown(int p,int l,int r)
{
    if(tag[p])
    {
        tag[p*2]+=tag[p];
        tag[p*2+1]+=tag[p];
        val[p*2]+=tag[p]*((l+r)/2-l+1);
        val[p*2+1]+=tag[p]*(r-(l+r)/2);
        maintain(p*2);
        maintain(p*2+1);
        tag[p]=0;
    }
}

void modify(int p,int l,int r,int ql,int qr,int v)
{
    if(l>qr || r<ql) return;
    if(l>=ql && r<=qr)
    {
        tag[p]+=v;
        val[p]+=v*(r-l+1);
        maintain(p);
    }
    else
    {
        pushdown(p,l,r);
        modify(p*2,l,(l+r)/2,ql,qr,v);
        modify(p*2+1,(l+r)/2+1,r,ql,qr,v);
        pushup(p);
    }
}

int query(int p,int l,int r,int ql,int qr)
{
    if(l>qr || r<ql) return 0;
    if(l>=ql && r<=qr) 
    {
        return val[p];
    }
    else
    {
        pushdown(p,l,r);
        return (query(p*2,l,(l+r)/2,ql,qr)+query(p*2+1,(l+r)/2+1,r,ql,qr))%mod;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) nxt[i]=i-1, g[i]=a[i];
    int top=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        while(top && a[sta[top]]<a[i])
        {
            modify(1,1,n,sta[top-1]+1,sta[top],-a[sta[top]]);
            --top;
        }
        modify(1,1,n,sta[top]+1,i,a[i]);
        sta[++top]=i;
        int pos=i;
        while(pos>0)
        {
            g[pos]=__gcd(g[pos],a[i]);
            while(__gcd(g[nxt[pos]],a[i])==__gcd(g[pos],a[i]) && nxt[pos]) 
            {
                nxt[pos]=nxt[nxt[pos]];
            }
            ans+=query(1,1,n,nxt[pos]+1,pos)*g[pos]%mod;
            ans%=mod;
            pos=nxt[pos];
        }
    }
    cout<<ans<<endl;
    return 0;
}