算法(单调队列思想+倍增)
单调队列 $O(n)$ 倍增$O(nlogn)$ 一共$O(nlogn)$
先单调队列扫一遍每一个点能跳到的第k个点,在用快速幂思想跳到每一个点上
核心 代码
void solve()
{
cin >> n >> k >> m;
for(int i = 1; i <= n; i ++) cin >> d[i];
int hh = 1, tt = k + 1;
for(int i = 1; i <= n; i ++)
{
while(tt + 1 <= n && d[tt + 1] - d[i] < d[i] - d[hh]) hh ++, tt ++;
if(d[tt] - d[i] > d[i] - d[hh]) ne[i] = tt;
else ne[i] = hh;
}
for(int i = 1; i <= n; i ++) ans[i] = i;
while (m)
{
if(m & 1)
for(int i = 1; i <= n; i ++) ans[i] = ne[ans[i]];
memcpy(tmp, ne, sizeof tmp);
for(int i = 1; i <= n; i ++)
ne[i] = tmp[tmp[i]];
m >>= 1;
}
for(int i = 1; i <= n; i ++)
cout << ans[i] << ' ';
cout << endl;
}