题意

·首先来理解一下题意，给定一序列长度为n的序列pi，每个pi对应一个结点i的坐标(离源头，即原点），对每个结点可以迁移到周围第k近的结点(对pj,即满足有k个结点pa, |pi - pa| <= |pi - pj|，若有两个结点都为第k近的，则选偏左的那个），求每个结点迁移m次之后的结点。

分析

·显然我们知道，对1<=k<=n<=10^6,m<=10^18,的数据范围，我我们直接暴力求第k近的点或暴力迁移m次都是会超时的。

·同时我们也知道，离每个结点第k近的结点是唯一的，即迁移方式是唯一的。

·所以关键就在于如何高效地求第k近的点和迁移m次

求第k近的点

·以样例的图为例

显然对任意一个结点，离其前k + 1近的点(包括该结点自身)都在一个长度为 k + 1 且包含了该点的区间里。

同时，如果我们知道了每个结点的前k+1近的点的区间，那离它第k近的结点只有可能在区间的两端(区间内的结点的距离都更近)，同时根据样例的情况我们也可发现，结点1和结点2的区间是完全相同的，这启发了我们使用滑动窗口。每次将滑动窗口更新到当前结点对应的区间然后看窗口两端的结点哪个离当前结点更远(一样远则选左边的)。

对滑动窗口如何更新，我们知道随着“当前结点”向右移动，对应的区间肯定也是以向右移动为趋势的，当我们的区间的最左节点不再属于离当前结点前k+1近的结点时,即右边的新结点离的更近时，滑动窗口右移。

	int hh = 1, tt = hh + k; // 头尾指针维护窗口
	for (int i = 1; i <= n; i ++ )
	{
		// 最左结点比右边新的结点远时，窗口右移，注意窗口不能超出序列范围
		while(hh < i && tt < n && (p[i] - p[hh]) > (p[tt + 1] - p[i])) 
		{
			hh ++ , tt ++ ;
		}
		// 选左右结点中更远的
		if ((p[i] - p[hh]) >= (p[tt] - p[i])) dp[i][0] = hh;  
		else dp[i][0] = tt;
		if (m & 1) plc[i] = dp[i][0];
	}

迁移m次

·对m = 10^18的数量级的求m次迁移后的状态的问题，我们常使用“倍增”的思路

·即我们知道每个节点迁移一次后的状态，使用二进制的思想

·那迁移 2^n 次，就可以认为是先迁移了2^(n - 1) 次， 然后再迁移2^(n - 1)次，即我们用

dp[i][j] 来存 第i个结点迁移2^j次的结果，则有，dp[i][j] = dp[dp[i][j - 1]][j - 1] (从i先迁移2^(j - 1) 次到dp[i][j - 1]， 再迁移2^(j - 1) 次)

这样我们就能表示出所有的 2^n 次迁移的状态，同时我们知道所有整数都是能用 2^n 二进制表示出来的

所以将m 拆分成若干个 2^n 相加即可(这个可以用类似快速幂的位运算右移， &1 看是不是二进制对应位实现)

	m >>= 1; // m 最低位为1的情况用于初始化了
	for (int j = 1; m; m >>= 1, j ^= 1)
	{
		// 因为dp[i][j] = dp[dp[i][j - 1]][j - 1]只与相邻深度的情况有关，这里为省空间只存了相邻的奇偶情况dp[N][2]
		for (int i = 1; i <= n; i ++ ) dp[i][j] = dp[dp[i][j ^ 1]][j ^ 1]; 
		if (m & 1) // 若当前位为1，迁移对应的 2^n 次 
		{
			for (int i = 1; i <= n; i ++ ) plc[i] = dp[plc[i]][j];
		}
	}

时间复杂度， 滑动窗口 O(n), 倍增O(nlogm), 故复杂度为O(nlogm)

空间复杂度, 这里只存了dp的相邻奇偶情况，为O(n)

完整代码

#include <iostream>
#include <cstdio>
#include <cstring> 
#include <algorithm>

using namespace std;
const int N = 1000010;

typedef long long ll;

int n, k;
ll m;
ll p[N];
int plc[N], dp[N][2];


int main()
{
	scanf("%d%d%lld", &n, &k, &m);
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%lld", &p[i]);
		plc[i] = i;
	}
	
	int hh = 1, tt = hh + k;
	for (int i = 1; i <= n; i ++ )
	{
		while(hh < i && tt < n && (p[i] - p[hh]) > (p[tt + 1] - p[i]))
		{
			hh ++ , tt ++ ;
		}
		if ((p[i] - p[hh]) >= (p[tt] - p[i])) dp[i][0] = hh;
		else dp[i][0] = tt;
		if (m & 1) plc[i] = dp[i][0];
	}
	m >>= 1;
	for (int j = 1; m; m >>= 1, j ^= 1)
	{
		for (int i = 1; i <= n; i ++ ) dp[i][j] = dp[dp[i][j ^ 1]][j ^ 1];
		if (m & 1)
		{
			for (int i = 1; i <= n; i ++ ) plc[i] = dp[plc[i]][j];
		}
	}
	
	for (int i = 1; i <= n; i ++ ) printf("%d ", plc[i]);
	puts("");
	
	return 0;
}

希望对大家有所帮助qwq.