【题解】CF538F：A Heap of Heaps

原题传送门
按照权值从小到大排序
找的是儿子中小于自己的有几个，这样我们就顺着枚举，满足权值递增，用树状数组维护个数，对于一个$x$，$k$叉树，儿子区间为$[xk+1-k,xk+1]$

注意要稳定排序

Code：

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
struct data{
	int val, id;
}a[maxn];
int tree[maxn], n, ans[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(data x, data y){ return x.val == y.val ? x.id < y.id : x.val < y.val; }
int lowbit(int x){ return x & -x; }
void update(int x){ for (; x <= n; x += lowbit(x)) ++tree[x]; }
int query(int x){ int s = 0; for (; x; x -= lowbit(x)) s += tree[x]; return s; }

int main(){
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = (data){read(), i};
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; ++i){
		update(a[i].id);
		int x = a[i].id;
		for (int j = 1; j < n && x * j - j + 1 < n; ++j) ans[j] += query(min(n, x * j + 1)) - query(x * j - j + 1);
	}
	for (int i = 1; i < n; ++i) printf("%d ", ans[i]);
	return 0;
}