hdu7107

本文主要是介绍hdu7107，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

好像和标算做法不太一样(?

考虑求出答案\(\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;
}

这篇关于hdu7107的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！