Codeforces

Luogu

分析

考虑求出一个 $H_i$ 表示有多少个 $[l,r]$ 满足 $f(l,r)\leq i$，则答案为
$$
\sum_{i=1}^{\max\{a\}}i\times(H_i-H_{i-1})
$$
考虑如何求 $H_i$。设 $nxt_l$ 表示最小的满足 $l\leq r,f(l,r)\leq i$ 的 $r$（若不存在则为 $n+1$）。则将 $l$ 作为左端点时右端点不能在 $nxt_l$ 左边，故有
$$
H_i=\sum_{i=1}^nn-nxt_i+1
$$
考虑快速求 $nxt_i$。考虑从大到小枚举 $i$，在 $i$ 减小时考虑 $nxt$ 的变化。

假设满足 $i|a_j$ 的 $j$ 为 $x_1,x_2,\cdots,x_m$，则 $[l,r]$ 外至多有这些数中的一个。因此 $nxt_{x_2+1..n}$ 会变成 $n+1$，$nxt_{x_1+1..x_2}$ 会与 $x_m$ 取 $\max$，$nxt_{1..x_1}$ 会与 $x_{m-1}$ 取 $\max$。

于是我们只需要写一个支持区间取 $\max$、区间求和的数据结构即可。可以用线段树实现，维护区间最大值、最小值、和，当最小值大于等于修改值时直接返回，当最大值小于修改值时直接区间赋值，否则向下递归。由于 $nxt$ 是不降的所以复杂度大概是对的。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,a[N]; ll H[N];
vector<int> v[N];

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2],minv[N<<2],setv[N<<2]; ll sumv[N<<2];
void pushup(int o) {
    maxv[o]=max(maxv[ls],maxv[rs]);
    minv[o]=min(minv[ls],minv[rs]);
    sumv[o]=sumv[ls]+sumv[rs];
}
void pushdown(int o,int l,int r) {
    if (setv[o]) { int mid=(l+r)>>1;
        setv[ls]=maxv[ls]=minv[ls]=setv[o];
        sumv[ls]=1ll*setv[o]*(mid-l+1);
        setv[rs]=maxv[rs]=minv[rs]=setv[o];
        sumv[rs]=1ll*setv[o]*(r-mid);
        setv[o]=0;
    }
}
void build(int o,int l,int r) {
    if (l==r) { maxv[o]=minv[o]=sumv[o]=l; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int ql,int qr,int w) {
    if (minv[o]>=w) return;
    if (ql<=l&&r<=qr&&maxv[o]<w) {
        setv[o]=maxv[o]=minv[o]=w,sumv[o]=1ll*w*(r-l+1); return;
    }
    int mid=(l+r)>>1; pushdown(o,l,r);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
#undef ls
#undef rs

int main() {
    n=read(); int lim=0;
    for (int i=1;i<=n;++i) {
        a[i]=read(); lim=max(lim,a[i]);
        for (int j=1;j*j<=a[i];++j) {
            if (a[i]%j) continue;
            v[j].push_back(i);
            if (j*j!=a[i]) v[a[i]/j].push_back(i);
        }
    }
    build(1,1,n);
    for (int i=lim;i;--i) {
        H[i]=1ll*n*n-sumv[1]+n;
        if (v[i].size()<=1) continue;
        int m=v[i].size();
        modify(1,1,n,v[i][1]+1,n,n+1);
        modify(1,1,n,v[i][0]+1,v[i][1],v[i][m-1]);
        modify(1,1,n,1,v[i][0],v[i][m-2]);
    }
    H[0]=1ll*n*n-sumv[1]+n;
    ll ans=0;
    for (int i=1;i<=lim;++i) ans+=i*(H[i]-H[i-1]);
    printf("%lld\n",ans);
    return 0;
}