n<=200000个数(<=200000),问所有的f(i,j)的和，f(i,j)表示去掉区间i到j后的剩余的数字中任选两个数的最大gcd
首先我们用(nxt_l)表示当(f(l,r)le i)时，(l)对应的右端点(r)最往左能取到哪里，初始时(nxt_l=l)，如果不存在合法右端点就记(nxt_l=n+1)。
然后考虑从大到小枚举(i)，当从(f(l,r)le i)变为(f(l,r)le i-1)时，我们需要删除(gcd=i)的贡献，找出(i)的倍数在原序列中的下标记为(x_1,x_2......x_m)，而我们新得到的区间([l,nxt_l'])肯定是要满足包含(m-1)个(x_i)的，不然答案就至少是(i)了，所以我们进行如下修改操作：
-
(lin(x_2,n])，(nxt_l=n+1)
-
(lin(x_1,x_2])，(nxt_l=max(nxt_l,x_m))
-
(lin[1,x_1])，(nxt_l=max(nxt_l,x_{m-1}))
2,3操作看似需要吉司机线段树来维护，但是我们冷静下来分析一波，(nxt)数组一定是单调不降，所以一定是进行区间的一段前缀覆盖，直接线段树上二分修改复杂度就是(O(nlogn))。
其实开始时(O(nsqrt n))处理每个数倍数的位置就已经足够了，但是也可以优化，因为我们最多只需要2个开头的和2个结尾的，那么直接合并(i)的倍数的集合就好了，复杂度是(O(nlogn))，我比较懒就直接写的第一种QAQ
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define zrt k << 1
#define yrt k << 1 | 1
const int N = 2e5;
using namespace std;
int n,a[N + 5],Mx;
long long ans,las;
vector <int> d[N + 5];
struct Seg
{
long long sm[N * 5 + 5],tag[N * 4 + 5];
int mi[N * 4 + 5],mx[N * 4 + 5];
void pushup(int k)
{
sm[k] = sm[zrt] + sm[yrt];
mi[k] = min(mi[zrt],mi[yrt]);
mx[k] = max(mx[zrt],mx[yrt]);
}
void build(int k,int l,int r)
{
if (l == r)
{
mx[k] = mi[k] = sm[k] = l;
return;
}
int mid = l + r >> 1;
build(zrt,l,mid);
build(yrt,mid + 1,r);
pushup(k);
}
void cha(int k,int l,int r,int z)
{
sm[k] = 1ll * (r - l + 1) * z;
mi[k] = mx[k] = z;
tag[k] = z;
}
void pushdown(int k,int l,int r,int mid)
{
if (tag[k])
{
cha(zrt,l,mid,tag[k]);
cha(yrt,mid + 1,r,tag[k]);
tag[k] = 0;
}
}
void modify(int k,int l,int r,int x,int y,int z)
{
if (x > y)
return;
if (r < x || l > y || mi[k] >= z)
return;
if (l >= x && r <= y && mx[k] <= z)
{
cha(k,l,r,z);
return;
}
if (l == r)
{
sm[k] = mi[k] = mx[k] = z;
return;
}
int mid = l + r >> 1;
pushdown(k,l,r,mid);
modify(zrt,l,mid,x,y,z);
modify(yrt,mid + 1,r,x,y,z);
pushup(k);
}
}tree;
int main()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]),Mx = max(Mx,a[i]);
for (int i = 1;i <= n;i++)
for (int j = 1;j * j <= a[i];j++)
if (a[i] % j == 0)
{
d[j].push_back(i);
if (j * j != a[i])
d[a[i] / j].push_back(i);
}
tree.build(1,1,n);
las = 1ll * n * (n + 1) - tree.sm[1];
int x1,x2,x3,x4;
for (int i = Mx;i >= 1;i--)
{
if (d[i].size() < 2)
continue;
x1 = *d[i].begin();
x2 = *(d[i].begin() + 1);
x3 = *(d[i].end() - 2);
x4 = *(d[i].end() - 1);
tree.modify(1,1,n,x2 + 1,n,n + 1);
tree.modify(1,1,n,x1 + 1,x2,x4);
tree.modify(1,1,n,1,x1,x3);
ans += (las - (1ll * n * (n + 1) - tree.sm[1])) * i;
las = 1ll * n * (n + 1) - tree.sm[1];
}
cout<<ans<<endl;
return 0;
}