这题可以求\(val\)为每一种\(i\)的\(f(l,r)\)数量,然后可以通过差分,改为\(val_{f(l,r)}\le i\)数量减\(val_{f(l,r)}\le i-1\)的数量.另外可以发现如果固定左端点\(l\),然后右端点\(r\)向右移动,那么所得到的\(val_{f(l,r)}\)一定是单调不增的,所以可以从小到大枚举\(i\),然后对每个左端点维护一个值,表示要满足\(val_{f(l,r)}\le i\),右端点最小是多少
如果把\(val_{f(l,r)}\le i\)改为\(val_{f(l,r)}\le i-1\),那么也就是右端点要移到区间内不超过两个数满足\(gcd\)为\(i\),放宽条件,可以看成要满足区间内不超过两个数为\(i\)的倍数,所以把权值为\(i\)的倍数的所有位置提出来,分别记为\(ps_1,ps_2,ps_3...ps_m\)
然后如果区间左端点\(l>ps_2\),那么这样的区间右端点在哪都不合法,我们可以把这样的左端点的右端点全改为\(n+1\);
如果\(ps_1<l\le ps_2\),那么要满足右端点右边没有是\(i\)的倍数的数,所以右端点应该在\(ps_m\)及以后,就把这些右端点和\(ps_m\)取\(\max\);
如果\(l\le ps_1\),那么要满足右端点右边最多有一个是\(i\)的倍数的数,所以右端点应该在\(ps_{m-1}\)及以后
然后就可以区间取\(max\)实现上述操作,可以知道\(val_{f(l,r)}\le i\)的数量就是\(\sum_{i=1}^{n}n-r_i+1\).实现时因为\(r_i\)是单调不增的,那么可以加一些剪枝,如果修改区间最小值\(\le\)当前修改值就直接退出,如果最大值\(<\)修改值就区间赋值,那么可以做到\(O(nlogn)\).还要注意\(i\)的倍数的位置集合的预处理,只有前两项和后两项是有用的,所以其他的可以不加入贡献
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=2e5+10;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m;
LL ans,nm[N],c1,c2;
vector<int> a[N],ps[N];
#define mid ((l+r)>>1)
LL s[N<<2];
int ma[N<<2],mi[N<<2],tg[N<<2];
void psup(int o)
{
s[o]=s[o<<1]+s[o<<1|1];
ma[o]=max(ma[o<<1],ma[o<<1|1]);
mi[o]=min(mi[o<<1],mi[o<<1|1]);
}
void cv(int o,int l,int r,int x)
{
s[o]=1ll*(r-l+1)*x;
ma[o]=mi[o]=x;
tg[o]=x;
}
void psdn(int o,int l,int r)
{
if(tg[o])
cv(o<<1,l,mid,tg[o]),cv(o<<1|1,mid+1,r,tg[o]),tg[o]=0;
}
void modif(int o,int l,int r,int ll,int rr,int x)
{
if(mi[o]>=x) return;
if(ll<=l&&r<=rr&&ma[o]<x){cv(o,l,r,x);return;}
psdn(o,l,r);
if(ll<=mid) modif(o<<1,l,mid,ll,rr,x);
if(rr>mid) modif(o<<1|1,mid+1,r,ll,rr,x);
psup(o);
}
void bui(int o,int l,int r)
{
if(l==r){s[o]=ma[o]=mi[o]=l;return;}
bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
psup(o);
}
int main()
{
n=rd();
for(int i=1;i<=n;++i)
{
int x=rd();
m=max(m,x);
a[x].push_back(i);
}
for(int i=1;i<=m;++i)
{
for(int j=1;i*j<=m;++j)
{
int nn=a[i*j].size();
if(nn<=4)
for(int k=0;k<nn;++k)
ps[i].push_back(a[i*j][k]);
else
{
ps[i].push_back(a[i*j][0]);
ps[i].push_back(a[i*j][1]);
ps[i].push_back(a[i*j][nn-2]);
ps[i].push_back(a[i*j][nn-1]);
}
}
}
bui(1,1,n);
for(int i=m;~i;--i)
{
nm[i]=1ll*(n+1)*n-s[1];
int nn=ps[i].size();
if(nn<=1) continue;
sort(ps[i].begin(),ps[i].end());
modif(1,1,n,1,ps[i][0],ps[i][nn-2]);
modif(1,1,n,ps[i][0]+1,ps[i][1],ps[i][nn-1]);
if(ps[i][1]<n) modif(1,1,n,ps[i][1]+1,n,n+1);
}
for(int i=1;i<=m;++i) ans+=1ll*i*(nm[i]-nm[i-1]);
printf("%lld\n",ans);
return 0;
}CF671C Ultimate Weirdness of an Array
原文：https://www.cnblogs.com/smyjr/p/11502926.html