好像和标算做法不太一样(?
考虑求出答案\(\geq i\)的区间个数
只需要对所有\(j\geq i\)求出答案至少为\(j\)的倍数的区间的并
考虑对于每个\(j\),把所有\(j\)的倍数的关键位置提出来
那么合法区间一定包含任意两个相邻的关键位置
把一个区间以\((l,r)\)作为二维平面的点
那么每个相邻位置的限制就是左上角的一个矩阵
相当于就是要求若干个左上矩阵的并的面积
考虑维护一个\((x,y)\)都递增的序列
每次插入一个只需要和前驱后继判一下,删除没有贡献的点即可
面积改变也可以根据前驱后继计算,用\(set\)维护即可
代码里维护的右下角
复杂度\(O(nlog^2n)\)
#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define y1 shinkle
#define fi first
#define se second
#define bg begin
namespace IO{
cs int RLEN=1<<22|1;
char ibuf[RLEN],*ib,*ob;
inline char gc(){
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
return f?res:-res;
}
inline ll readll(){
char ch=gc();
ll res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
return f?res:-res;
}
inline char readchar(){
char ch=gc();
while(isspace(ch))ch=gc();
return ch;
}
inline int readstring(char *s){
int top=0;char ch=gc();
while(isspace(ch))ch=gc();
while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();
s[top+1]='\0';return top;
}
}
using IO::read;
using IO::readll;
using IO::readchar;
using IO::readstring;
template<typename tp>inline bool chemx(tp &a,tp b){return (a<b)?(a=b,1):0;}
template<typename tp>inline bool chemn(tp &a,tp b){return (a>b)?(a=b,1):0;}
cs int N=100005;
ll ans[N];
int a[N],n,p[N];
vector<int> ps[N];
ll res;
set<pii> st;
#define It set<pii>::iterator
void clear(){
for(int i=1;i<=n;i++)ans[i]=0,p[i]=0,ps[i].clear();
st.clear();res=0;
}
void add(int l,int r){
pii x=pii(n+1-l,n+1-r);
It it=st.lower_bound(x),itp=it,nit,pt;
if((*it).fi==x.fi&&(*it).se>x.se)return;
itp--;
if((*itp).fi<=x.fi&&(*itp).se>=x.se)return;
while((*it).fi>=x.fi&&(*it).se<=x.se){
nit=it,++it;
pt=nit;pt--;
res-=1ll*((*nit).se-(*pt).se)*((*it).fi-(*nit).fi);
st.erase(nit);
}
st.insert(x);
nit=st.find(x);
itp=nit;itp--;
it=nit;++it;
res+=1ll*(x.se-(*itp).se)*((*it).fi-x.fi);
}
inline void solve(){
n=read();res=0;
for(int i=1;i<=n;i++)a[i]=read(),p[a[i]]=i;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
ps[i].pb(p[j]);
for(int i=1;i<=n;i++)
sort(ps[i].bg(),ps[i].end());
st.insert(pii(0,0));
st.insert(pii(n+1,n+1));
for(int i=n;i;i--){
for(int j=0;j+1<ps[i].size();j++)
add(ps[i][j],ps[i][j+1]);
ans[i]=res;
}
for(int i=1;i<n;i++)ans[i]-=ans[i+1];
for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
clear();
}
int main(){
#ifdef Stargazer
freopen("lx.in","r",stdin);
freopen("my.out","w",stdout);
#endif
int T=read();
while(T--)solve();
// cerr<<clock()<<'\n';
return 0;
}