题解：CF538F A Heap of Heaps

对于点

u

，它在

k

叉堆中的父亲是

\frac{u+k-2}{k}

。注意到对于某个点，它在一段分叉数连续的堆中的父亲是一样的。这个点对于这一段答案的贡献也是一样的。

考虑整除分块。对每段贡献做差分，最后前缀和出来所有答案。

复杂度

O(n\sqrt{n})

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 200100;
int n;
int a[N],s[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        int k=1,f=0;
        while(k<=i-2){
        	f=(i+k-2)/k;
            s[k]+=(a[f]>a[i]);
            k=(i-2)/((i-2)/k)+1;
            s[k]-=(a[f]>a[i]);
        }
        s[k]+=(a[1]>a[i]);
    }
    for(int i=1;i<n;i++){
        s[i]+=s[i-1];
        cout<<s[i]<<' ';
    }
    return 0;
}

题解：CF538F A Heap of Heaps

文章操作

相关推荐

评论

题解：CF538F A Heap of Heaps