大意

一共 $n$ 个点，将这 $n$ 个点进行 $m$ 次操作，每次同时将 $n$ 个点移动到离这个点距离第 $k$ 小的点，问最后这 $n$ 个点的坐标。

思路

根据题目，我们可以想出，用单调队列 + 快速幂就可以解决此问题。我们用 $nxt_i$ 表示距离第 $i$ 个点的第 $k$ 小的点，用 $ans_i$ 去存答案，每次移动用快速幂更新即可。

单调队列显然用于初始化 $nxt$, 也就需要让 $head$ 和 $tail$ 相差 $k$。

其他就没什么了，具体请参见代码。

#include <bits/stdc++.h
using namespace std;
typedef long long ll; //！！！ 
ll n, m;
ll k;
ll a[1000001];
int nxt[1000001]; //nxt[i]表示距离第i个点的第k小的点的编号 
int tmp[1000001];
int ans[1000001]; //存答案 
int main()
{
	speed: std::ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); //加速 
	cin >> n >> k >> m;
	for(int i = 1; i <= n; i++) //读入坐标 
		cin >> a[i];
	nxt[1] = k + 1; //注意！是k + 1而不是1！！！ 
	int head = 1, tail = k + 1; //队首，队尾，距离保持k 
	for(int i = 2; i <= n; i++) //进行初始（单调队列） 
	{
		while(tail + 1 <= n && a[i] - a[head] > a[tail + 1] - a[i]) head++, tail++;
		//下面开始记录 
		if(a[i] - a[head] >= a[tail] - a[i]) nxt[i] = head;
		else nxt[i] = tail;
	}
	for(int i = 1; i <= n; i++)
		ans[i] = i; //移动0次就是原先的样子 
	while(m) //快速幂 
	{
		if(m & 1) //相当于m % 2 == 1 
			for(int i = 1; i <= n; i++) //肯定要更新啊！ 
				ans[i] = nxt[ans[i]];
		memcpy(tmp, nxt, sizeof(tmp)); //暂时存一下，方便后面使用 
		for(int i = 1; i <= n; i++)
			nxt[i] = tmp[tmp[i]]; //更新下一个移动到的点 
		m >>= 1; //相当于m /= 2 
	}
	for(int i = 1; i <= n; i++)
		cout << ans[i] << " ";
	return 0;
}