题解：CF538F A Heap of Heaps

MutU · 2025-08-18 20:07:06 · 题解

对于点 u，它在 k 叉堆中的父亲是 \frac{u+k-2}{k}。注意到对于某个点，它在一段分叉数连续的堆中的父亲是一样的。这个点对于这一段答案的贡献也是一样的。

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

复杂度 O(n\sqrt{n})。

#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;
}