原题地址
题目描述
给定一个长度为$n$的数列,对于 $1~n-1$ 的所有 $k$,建造一个完全$k$叉数。对于每一个$k$,求父亲比儿子大的节点对数。
样例
输入
5
1 5 4 3 2
输出
3 2 1 0
样例解释
![](https://codeforces.com/predownloaded/9c/3d/9c3d8c9512356fd42aabc8f05013b3d8ec82ec68.png)
![](https://codeforces.com/predownloaded/39/e3/39e30d211699c5981994b57763cc74ed82ed67eb.png)
![](https://codeforces.com/predownloaded/c9/18/c918380bce40392c703fb4212c0d856a3e1a412a.png)
![](https://codeforces.com/predownloaded/97/1c/971cfdbbd7379feaf56ca39c72c7ae53340584a0.png)
思路
我们很容易发现,对于一个点,一定范围的k内它的父亲节点位置是相同的。因为题目给了点$i$父亲的定义是$(i-2)/k+1$,你会发现取值的种类是$sqrt(n)$级别的。。。
所以我们直接枚举对于每个节点的不同的父亲,用差分数组维护区间加,最后求前缀和得到答案。
代码
#include
#define ll long long
#define maxn 200100
using namespace std;
ll a[maxn],sum[maxn],n;
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=2;i<=n;i++){
int v=i-2,t;
for (int j=1;j<=v;j=t+1){
t=v/(v/j);
if (a[v/j+1]>a[i]) sum[j]++,sum[t+1]--;
}
if (a[1]>a[i]) sum[i-1]++,sum[n]--;
}
for (int i=1;i