问题描述
现在有一个长度为n的数组 a1, a2, ..., an 。然后对于k从1到 n-1分别对该数组建k叉堆。现在要统计对于每一个k叉堆，里面有多少结点是不满足最小堆的性质的。即值比父亲的要小的结点有多少个。
k叉堆的定义是这样的：数组的下标从1到n编号，对于某一个编号为v的结点，他的k个儿子编号是 k(v − 1) + 2, ..., kv + 1 （如果其中某些编号超出n，那些编号就不要）。在k叉堆中，除了根以外，每一个结点都有一个父亲。p(v)表示结点v的父亲。那么一个非根结点不满足最小堆性质当且仅当 av < ap(v) 。
输入格式
单组测试数据。
第一行有一个整数 n (2≤n≤2*10^5)。
第二行有n个用空格分开的整数a1, ..., an (-109≤ai≤109)。
输出格式
输出n-1个数字，第k个数字代表k叉堆中不满足最小堆性质的结点数目 （k=1, 2, ..., n-1）。
样例输入
5
1 5 4 3 2
样例输出
3 2 1 0
解析
一个节点不合法当且仅当它的儿子节点中存在比它小的值。观察发现，一个节点在 (k) 确定时，它的儿子区间是可以直接算出来的。我们不妨按权值从小到大依次加入点，对每一个点枚举 (k) ，判断对应的儿子区间里是否有比他小的值。这个用树状数组就可以高效的实现。
对于每一个点，当 (k) 大于一定值的时候整个儿子区间就会到 (n) 外面去。所以枚举 (k) 是 (O(nlog n)) 的。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 300002
using namespace std;
struct node{
int v,p;
}a[N];
int n,i,j,k,c[N],ans[N];
int read()
{
char c=getchar();
int w=0,f=1;
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w*f;
}
int lowbit(int x)
{
return x&(-x);
}
int ask(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];
return ans;
}
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y;
}
int my_comp(const node &a,const node &b)
{
return a.v<b.v;
}
int main()
{
n=read();
for(i=1;i<=n;i++) a[i].v=read(),a[i].p=i;
sort(a+1,a+n+1,my_comp);
for(i=k=1;i<=n;i++){
int pos=a[i].p+1;
for(j=1;j<n;j++){
if(pos>n){
if(pos-j+1<=n) ans[j]+=ask(n)-ask(pos-j);
else break;
}
else ans[j]+=ask(pos)-ask(pos-j);
pos+=a[i].p;
}
if(a[i+1].v!=a[i].v){
while(k<=i) add(a[k].p,1),k++;
}
}
for(i=1;i<n;i++) printf("%d ",ans[i]);
puts("");
return 0;
}