Solution
用一个双向链表维护原数组,从小到大计算,每次删去,这样链表里的每个数都比它大了
用 的时间分别向左向右找链表中 k 个数的位置,可以把一边记录一下
然后相互匹配,使得匹配到的两个数在链表上距离为 k - 1 ,然后乘法原理统计贡献即可
Code
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 300005;
int n, K, p[MAXN];
int pos[MAXN], ans[MAXN];
int l[MAXN], r[MAXN];
int dis[MAXN];
inline void Solve(int x) {
int res = 0, p = pos[x];
for (int i = 0; i <= K; ++ i)
dis[i] = 0;
for (int t = 0; t < K; ++ t) {
if (!p) break;
dis[t] = p - l[p];
p = l[p];
}
p = pos[x];
for (int t = K - 1; ~t; -- t) {
if (p > n) break;
res += dis[t] * (r[p] - p);
p = r[p];
}
p = pos[x];
r[l[p]] = r[p], l[r[p]] = l[p];
ans[pos[x]] = res;
}
signed main()
{
scanf ("%lld%lld", &n, &K);
for (int i = 1; i <= n; ++ i)
scanf ("%lld", p + i), pos[p[i]] = i,
l[i] = i - 1, r[i] = i + 1;
for (int i = 1; i <= n; ++ i)
Solve(i);
for (int i = 1; i <= n; ++ i)
printf ("%lld ", ans[i]);
return puts(""), 0;
}