Description
有一个小根堆,这个堆变成了一个 (k) 叉堆(形式转化,逐层排布),但这样不一定是合法的(即有若干个节点小于它的父亲)。问现在这个堆有多少不合法的元素。对所有 (k) 输出结果。
Solution
(x) 号点在 (k) 叉树上的父亲是 ([frac {x-2} {k}]+1)
枚举儿子来计算答案,显然可以整除分块,用差分计算答案,复杂度为 (O(n sqrt n))
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a[N],n,ans[N];
void modify(int l,int r)
{
ans[l]++;
ans[r+1]--;
}
void solve()
{
for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)
{
int l=1,r=1;
while(l<=(i-2))
{
r=(i-2)/((i-2)/l);
int p=(i-2)/l+1;
if(a[i]<a[p])
{
modify(l,r);
}
l=r+1;
}
if(a[1]>a[i]) ans[l]++;
}
solve();
for(int i=1;i<n;i++) cout<<ans[i]<<" ";
}