出处： Codeforces
主要算法：树状数组/线段树
难度：4.6
思路分析：
在没看到数据范围之前真是喜出望外，直到发现O(n^2)会被卡……
其实也不是特别难的
我们要做的事情就是对于每一个节点v，求出当k分别取\(1,2,3,...,n\)时比v的权值小的v的儿子数量。既然要求每个节点的，那n自然是要扫的。那有没有能够在O(log n)复杂度内求出权值小于v的节点数量的方法呢？这自然让我们联想到了O(log n)的数据结构——树状数组或者线段树。
数组a[i]保存节点的信息。a[i].x表示权值，a[i].idx表示编号（位置）。首先将数组a按照x从小到大进行排序，并在处理好每一个节点后用树状数组更新bit[a[i].idx]，让它+1。bit[i]维护的其实就是位置i是否被更新过。那么设想一下，因为a数组是按照权值进行排序的，所以已经被更新过的点的权值一定<=a[i]。因此我们可以查询区间[left,right]（表示节点v的子节点的位置的左右位置的最值），得到的答案就是小于节点v权值的子节点的数量。而由于此序列是一定的，无论k怎么变，只需要改变一下left和right就可以得到不同的堆的答案了。所以我们进行如下操作：
\(ans[k] += Query(right) - Query(left-1);\)
我想意义已经很清楚了。
最后有一个复杂度的计算问题：我在外层扫描了节点i，内层扫描了堆的叉数k，又做了bit，为什么复杂度会是\(O(n log n)\)？不应该是\(O(n^2 log n)\)吗？但是总共就n个节点，并且k越大叶子就越多，所以到后来几乎一进循环就会跳出。所以复杂度就等同于\(O(n)\)了
代码注意点：
排序改成双关键字。因为要先更新父亲，再更新儿子。不然与父亲节点权值相同的儿子会被算为违反的。
Code
/*By QiXingzhi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int N = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
struct Number{
int x,idx;
}a[N];
int n,m,left,right;
int bit[N],ans[N];
inline bool comp(Number& a, Number& b){
if(a.x == b.x) return a.idx < b.idx;
return a.x < b.x;
}
inline int GetLeft(int v, int k){
return (k * (v-) + );
}
inline int GetRight(int v, int k){
return ((k * v) + );
}
inline int Query(int x){
int i = x;
int res = ;
while(i > ){
res += bit[i];
i -= i & (-i);
}
return res;
}
inline void Update(int x, int k){
int i = x;
while(i <= N){
bit[i] += k;
i += i & (-i);
}
}
int main(){
n = r;
for(int i = ; i <= n; ++i){
a[i].x = r;
a[i].idx = i;
}
sort(a+,a+n+,comp);
for(int i = ; i <= n; ++i){
for(int k = ; k < n; ++k){
left = GetLeft(a[i].idx,k);
right = GetRight(a[i].idx,k);
if(left > n) break;
if(right > n) right = n;
ans[k] += Query(right) - Query(left-);
}
Update(a[i].idx, );
}
for(int i = ; i < n; ++i){
printf("%d ", ans[i]);
}
return ;
}