Description：

一条河上有 $n$ 个石块，每次跳到距这块石头第 $k$ 远的石头上去，问在每块石头上跳 $m$ 次跳到的最终位置。

$1\le n,k \le 10^6,1\le m \le 10^{18}$

Solution：

首先如果找到了第 $k$ 远的石头，那么可以像快速幂一样拆开二进制位倍增。

求第 $k$ 远的石头可以用队列，先把前 $k+1$ 个放进队列，然后每次调整左右端点使得队列中始终为距第 $i$ 个点最近的 $k+1$ 个点（包括第 $k$ 个），左右端点的变化显然是单调的，只要弹队头压队尾即可，第 $k$ 个就是队头队尾距离远的那个。

时间复杂度 $O(n+n\log m)$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,k;

typedef long long ll;

ll m;

#define MAXN 1000010

ll a[MAXN];

int f[MAXN],tmp[MAXN];

int q[MAXN],head,tail;

int pos[MAXN];

int main()

{

    scanf("%d%d%lld",&n,&k,&m);++k;

    for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

    int cur;

    head = 1;tail = 0;

    for(cur = 1;cur <= min(n,k);++cur)q[++tail] = cur;

    for(int i = 1;i <= n;++i)

    {

        while(cur <= n && abs(a[cur] - a[i]) < abs(a[i] - a[q[head]]))

        {

            ++head;

            q[++tail] = cur++;

        }

        if(abs(a[q[head]] - a[i]) >= abs(a[q[tail]] - a[i]))f[i] = q[head];

        else f[i] = q[tail];

    }

    for(int i = 1;i <= n;++i)pos[i] = i;

    while(m > 0)

    {

        if(m & 1)

        {

            for(int i = 1;i <= n;++i)

            {

                pos[i] = f[pos[i]];

            }

        }

        for(int i = 1;i <= n;++i)tmp[i] = f[i];

        for(int i = 1;i <= n;++i)f[i] = tmp[f[i]];

        m = m >> 1;

    }

    for(int i = 1;i <= n;++i)printf("%d ",pos[i]);

    puts("");

    return 0;

}