好像和标算做法不太一样(?
考虑求出答案\(\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; }