原题地址

题目描述

给定一个长度为$n$的数列,对于 $1~n-1$ 的所有 $k$,建造一个完全$k$叉数。对于每一个$k$,求父亲比儿子大的节点对数。

样例

输入

输出

样例解释



思路

我们很容易发现,对于一个点,一定范围的k内它的父亲节点位置是相同的。因为题目给了点$i$父亲的定义是$(i-2)/k+1$,你会发现取值的种类是$sqrt(n)$级别的。。。
所以我们直接枚举对于每个节点的不同的父亲,用差分数组维护区间加,最后求前缀和得到答案。

代码