【题解】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; }