P3509 [POI 2010] ZAB-Frog - 洛谷
分析
-
p[i]数组给定：预处理nxt[i]为距离p[i]第k近的序号。
-
nxt[i]的预处理：显然，nxt[i]是包含 i 的长度为k+1的子区间的权较大端点中的权最小的点。
考虑滑动窗口维护。
- 跳跃m步的查询：m范围很大，我们用类似快速幂的方法查询，将复杂度降至O(log m)。
代码分析
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6+10;int n, k, m;
int p[N];
int r[N];
int tmp[N];
int nxt[N];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> k >> m;for (int i = 1; i <= n; i++)cin >> p[i], r[i] = i;int head = 1;int tail = k + 1;for (int i = 1; i <= n; i++){while (tail + 1 <= n && p[tail + 1] - p[i] < p[i] - p[head]) head++, tail++;if (p[tail] - p[i] > p[i] - p[head]) nxt[i] = tail;else nxt[i] = head;}// for(int i=1;i<=n;i++)
// cout<<nxt[i]<<" ";
// cout<<endl;for (int mm = m; mm; mm >>= 1){if (mm & 1)for (int i = 1; i <= n; i++)r[i] = nxt[r[i]];for (int i = 1; i <= n; i++)tmp[i] = nxt[nxt[i]];for (int i = 1; i <= n; i++)nxt[i] = tmp[i];}for (int i = 1; i <= n; i++)cout << r[i] << " ";return 0;
}