【Codeforces 671C】Ultimate Weirdness of an Array
线段树。
题目大意：
给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,\ldots,a_n$。
定义 $f(l,r)$ 表示去掉 $a_{l..r}$ 后，从 $a$ 中选择两个数，它们的 $\gcd$ 的最大值。
求 $\sum\limits_{\ \ 1\leq l\leq r\leq n\\ r-l+1\leq n-2}f(l,r)$ 的值。
题解：
令 $f(i,j)$ 表示去掉 $a_i,a_{i+1},a_{i+2},\ldots,a_j$ 后，剩下的数中选两个位置不同的数，它们的 $\gcd$ 最大值。
令 $h_i$ 表示 $f(l,r)\leq i$ 的 $l,r$ 对数。那么我们要求的答案就为 $\sum\limits_{i=1}^{200000} (h_i-h_{i-1})\times i$。
再令 $nx[l]$ 表示满足 $f(l,r)\leq i$ 的最小的 $r$。那么有 $h_i=\sum_{l=1}^n n-nx[l]+1$。
这里的 $h_i,nx[l]$ 都是随着 $i$ 的增大而单调不降的，并且 $nx$ 本身单调不降。
我们考虑 $i$ 减 $1$ 之后，$nx$ 会如何变化。
用一个 vector 记录含有因子 $i$ 的数的下标 $x_1,x_2,x_3,\ldots,x_k$。当 $i$ 减去 $1$ 之后，区间外就最多只能有 $1$ 个数含有因子 $i$。
所以对于 $l\in[x_2+1,x+k]$，$nx[l]$ 要变成 $n+1$。对于 $l\in[x_1+1,x_2]$，$nx[l]$ 要对 $x_k$ 取 $\max$。对于 $l\in[1,x_1]$，$nx[l]$ 要对 $x_{k-1}$ 取 $\max$。实际上每个因数只需要记四个位置。
由于 $nx$ 在任意时刻都满足单调不降，所以可以直接使用线段树进行区间对一个数取 $\max$，全局求和的操作。也可以使用其他数据结构。
求出 $h$ 之后进行差分，然后可以计算答案。
时间复杂度 $O(n\log n+n\cdot d(a))$。
Code：
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int fst[N],sec[N],x,n,tag[N<<2],mx[N],cmx[N],Min[N<<2],Max[N<<2],a[N];
LL d[N<<2],h[N];
vector<int>fc[N];
void build(int l,int r,int o){
Min[o]=l,Max[o]=r;
if(l==r)d[o]=l;else{
const int mid=l+r>>1;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
d[o]=d[o<<1]+d[o<<1|1];
}
}
inline void pushdown(int o,int len){
int&v=tag[o];
Min[o<<1]=Max[o<<1]=Min[o<<1|1]=Max[o<<1|1]=tag[o<<1]=tag[o<<1|1]=v;
d[o<<1]=(len+1LL>>1)*v,d[o<<1|1]=(len>>1)*(LL)v;
v=0;
}
void modify(int l,int r,int o,const int&L,const int&R,const int&val){
if(Min[o]>=val)return;
const int mid=l+r>>1;
if(L<=l&&r<=R){
if(Max[o]<=val){
Min[o]=Max[o]=tag[o]=val,d[o]=val*(r-l+1LL);
return;
}
}
if(tag[o])pushdown(o,r-l+1);
if(L<=mid)modify(l,mid,o<<1,L,R,val);
if(mid<R)modify(mid+1,r,o<<1|1,L,R,val);
d[o]=d[o<<1]+d[o<<1|1],Min[o]=Min[o<<1],Max[o]=Max[o<<1|1];
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
int mxw=0;
for(int i=1;i<=n;++i){
cin>>a[i];
if(a[i]>mxw)mxw=a[i];
}
for(int i=1;i<=mxw;++i)
for(int j=i;j<=mxw;j+=i)
fc[j].push_back(i);
for(int i=1;i<=n;++i)
for(int j=0;j<fc[a[i]].size();++j){
int x=fc[a[i]][j];
if(!fst[x])fst[x]=i;else
if(!sec[x])sec[x]=i;
cmx[x]=mx[x],mx[x]=i;
}
build(1,n,1);
for(int x=mxw+1;x;--x){
if(sec[x]){
if(sec[x]<n)
modify(1,n,1,sec[x]+1,n,n+1);
modify(1,n,1,fst[x]+1,sec[x],mx[x]);
modify(1,n,1,1,fst[x],cmx[x]);
}
h[x]=(n+1LL)*n-d[1];
}
LL ans=0;
for(int x=mxw+1;x;--x)ans+=(h[x]-h[x-1])*(LL)(x-1);
cout<<ans<<'\n';
return 0;
}