题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7107
经典统计所有 ((l,r)) 区间的问题，所以固定右端点进行考虑
观察到如果固定右端点 (r)，(l) 到 (r) 区间内的 (gcd) 最大值随着 (l) 从右到左而逐渐变大
同时，如果区间 ([i,j]) 内的最大公因数为 (x)，则 ([i,j]) 内一定至少存在两个 (x) 的倍数
于是我们考虑从大到小枚举 (gcd)，同时维护每个右端点当前未确定答案的最左边的位置（([l,r]) 中 (gcd) 越大的 (l) 越靠左），于是相当于每次遍历 (gcd) 倍数所在的位置 (g[i])，将 ([g[i+1],n]) 内的答案与 (g[i]+1) 取最大值（当前已确定固定的 (r) 的左端 (l) 为 ([1,g[i]])），可以使用 (Segment tree beats) 解决
又可以注意到，对于将要进行区间取最大值操作的 ([g[i+1],n]) 这段区间，左端点固定，则 (r) 越大，区间中最大 (gcd) 越大，所以 ([g[i+1],n]) 区间内维护的最左端的位置也是单调递增的，所以只需要在线段树内二分出这段区间中最后一个需要更新的位置，使用区间覆盖更新即可，每个 (gcd) 操作前后线段树维护的最左端位置的和的差（每个固定右端点更新的区间长度和）即为该 (gcd) 的答案
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int T, n;
int a[maxn], p[maxn];
ll ans[maxn];
vector<int> fac[maxn];
struct Node{
int tag, mi;
ll sum;
}t[maxn<<2];
void pushup(int i){
t[i].mi = min(t[i<<1].mi, t[i<<1|1].mi);
t[i].sum = t[i<<1].sum + t[i<<1|1].sum;
}
void build(int i, int l, int r){
if(l == r){
t[i].tag = 0;
t[i].mi = 1;
t[i].sum = 1ll;
return;
}
int mid = (l+r) >> 1;
build(i<<1, l, mid); build(i<<1|1, mid+1, r);
pushup(i);
}
void pushdown(int i, int l, int r){
if(t[i].tag){
t[i<<1].tag = t[i<<1|1].tag = t[i].tag;
int mid = (l+r) >> 1;
t[i<<1].mi = t[i].tag;
t[i<<1|1].mi = t[i].tag;
t[i<<1].sum = 1ll * t[i].tag * (mid-l+1);
t[i<<1|1].sum = 1ll * t[i].tag * (r-mid);
t[i].tag = 0;
}
}
void modify(int i, int k, int l, int r, int x, int y){
if(x <= l && r <= y){
t[i].tag = k;
t[i].mi = k;
t[i].sum = 1ll * k * (r-l+1);
return;
}
pushdown(i, l, r);
int mid = (l+r) >> 1;
if(x <= mid) modify(i<<1, k, l, mid, x, y);
if(y > mid) modify(i<<1|1, k, mid + 1, r, x, y);
pushup(i);
}
int find(int i, int k, int l, int r, int x){
if(l == r){
return l;
}
pushdown(i, l, r);
int mid = (l+r) >> 1;
int pos = -1;
if(t[i<<1|1].mi < k) pos = find(i<<1|1, k, mid+1, r, x);
if(pos != -1) return pos;
if(x <= mid && t[i<<1].mi < k) pos = find(i<<1, k, l, mid, x);
return pos;
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
T = read();
while(T--){
memset(t, 0, sizeof(t));
memset(ans, 0, sizeof(ans));
n = read();
for(int i = 1 ; i <= n ; ++i) {
a[i] = read(), p[a[i]] = i;
}
for(int i = 1 ; i <= n ; ++i){
fac[i].clear();
for(int j = i ; j <= n ; j += i){
fac[i].push_back(p[j]);
}
sort(fac[i].begin(), fac[i].end());
}
build(1, 1, n);
for(int g = n ; g >= 1 ; --g){
ll sum = t[1].sum;
for(int i = 0 ; i < fac[g].size()-1 ; ++i){
int pos = find(1, fac[g][i]+1, 1, n, fac[g][i+1]);
if(pos != -1 && pos >= fac[g][i+1]) modify(1, fac[g][i]+1, 1, n, fac[g][i+1], pos);
}
ans[g] = t[1].sum - sum;
}
for(int g = 1 ; g <= n ; ++g){
printf("%lld
", ans[g]);
}
}
return 0;
}