[CF 538F] A Heap of Heaps

作法：

首先把數列換成 0-base 的，那麼可以得到節點 $x$ 在構成 $y$ 元樹時的祖先就是 $\left \lfloor \frac{x-1}{y} \right \rfloor$ ，而由這件事就可以得到：當 $y$ 從 $1$ 慢慢變大到 $n-1$ 時， $\left \lfloor \frac{x-1}{y} \right \rfloor$ 的值只會改變 $O( \sqrt{ x } )$ 次，所以就可以把所有 $\left \lfloor \frac{x-1}{y} \right \rfloor$ 值一樣的 $y$ 們和在一起算，這樣就可以在 $O( n \sqrt{ n } )$ 的時間內算完答案了。一樣的技巧也出現在 POI 21 Stage 3 Solar Panels 和 POI 14 Stage 1 Queries ( HOJ 22 駭客 )  中，詳解分別可以參考這裡和這裡。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
int a[maxn],ans[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;)
        {
            int q=(i-1)/j ;
            int j2= (q==0?n-1:(i-1)/q) ;
            if(a[q]>a[i]) ans[j]++ , ans[j2+1]-- ;
            j=j2+1 ;
        }
    }
 
    for(int i=1,s=0;i<n;i++)
        printf("%d%c",s+ans[i],i==n-1?'\n':' ') ,
        s+=ans[i] ;
}