[POI2010] ZAB-Frog

题面翻译

有 $n$ 个点，升序给出每个点到起点的距离。有编号为 $1 \sim n$ 的 $n$ 只青蛙分别在第 $1 \sim n$ 个点上，每次它们会跳到距离自己第 $k$ 近的点上。

如果有相同距离的点，就跳到下标更小的点上。

求跳 $m$ 次之后，第 $i$ 只的青蛙在哪个点上。

输入共一行三个整数：代表 $n, k, m$。

输出共一行 $n$ 个整数，代表每只青蛙最终所处在的点。

题目描述

On the bed of one particularly long and straight Byteotian brook there lie $n$ rocks jutting above the water level. Their distances from the brook's spring are $p_1 < p_2 < \cdots < p_n$ respectively. A small frog sitting on one of these is about to begin its leaping training. Each time the frog leaps to the rock that is the -th closest to the one it is sitting on. Specifically, if the frog is sitting on the rock at position $p_i$, then it will leap onto such $p_j$ that:

$$ |\{ p_a : |p _ a - p _ i| < |p_j - p_i| \}| \le k \text{ and } |\{ p_a : |p _ a - p _ i| \le |p_j - p_i| \}| > k $$

If $p_j$ is not unique, then the frog chooses among them the rock that is closest to the spring. On which rock the frog will be sitting after $m$ leaps depending on the rock is started from?

输入格式

The first line of the standard input holds three integers, $n$, $k$ and $m$ ($1 \le k < n \le 1 \, 000 \, 000, 1 \le m \le 10^{18}$), separated by single spaces, that denote respectively: the number of rocks, the parameter $k$, and the number of intended leaps. The second line holds $n$ integers $p_j$ ($1 \le p_1 < p_2 < \cdots < p_n \le 10^{18}$), separated by single spaces, that denote the positions of successive rocks on the bed of the brook.

输出格式

Your program should print a single line on the standard output, with $n$ integers $r_1, r_2, \cdots, r_n$ from the interval $[1, n]$ in it, separated by single spaces. The number $r_i$ denotes the number of the rock that the frog ends on after making $m$ leaps starting from the rock no. $i$ (in the input order).

样例 #1

样例输入 #1

5 2 4
1 2 4 7 10

样例输出 #1

1 1 3 1 1

提示

样例 #1 解释：

The figure presents where the frog leaps to (in a single leap) from each and every rock.

题目分析

仔细阅读，可知题意为：求出跳跃m步后所处的位置。

从数据范围中可知m的范围很大为$10^{18}$。暴力去模拟跳跃必然是会超时的，那么如何进行优化？对于加速跳跃这一过程容易想到倍增优化，设计$nxt[位置][跳跃次数]$ ，nxt[i][j] 为从i点跳跃$2^j$次到达的位置。更新过程为 $nxt[i][j]=nxt[nxt[i][j-1]][j-1]$ 。更新预处理的复杂度为 $O(n\log m)$ 。

在已知nxt[][] 的基础上，要求解跳跃m次后的位置可对m进行二进制拆分。单次查询复杂度为 $O(\log m)$

int query(int pos,int m){
    int lg=log2(m);
    for(int i=0;i<=lg;i++){
        if((m>>i)&1){
            pos=nxt[pos][i];
        }
    }
    return pos;
}

逻辑通。解决剩下的问题：如何求出从每个位置跳一次到达的位置？根据题意，到达的位置为离$i$第$k$近的位置。题目中对于位置$p_i$ 有特殊性质：升序。那么对于离第$i$个元素的前$k$近的元素必然分布在$i$的两侧，且形成一个包含$i$长度为$k+1$的连续区间，设该区间左右端点为$L$和$R$。第$k$近的元素必然在端点处。那么如果 $p_R-p_i>p_i-p_L$ 则$p[R]$ 为第$k$ 近的元素，否则是 $p[L]$ 。

对于下一个元素 $p_{i+1}$ 的前$k$小元素形成的区间$[L_{i+1},R_{i+1}]$ 一定不会在上一个区间$[L_i,R_i]$的左侧，也就是 $L_i\le L_{i+1},R_i\le R_{i+1}$ 。

p[]是升序的，$p[i]<p[i+1]$ ，比较$p[i]-p[L]$和$p[i+1]-p[L]$ 与左端点的距离在变大，比较$p[R]-p[i]$和$p[R]-p[i+1]$ 与有端点的距离在变小，所以如果要更新连续区间，必然是要舍弃左端点的元素的，所以整体区间是在上一个区间的基础上右移，两个端点是同向移动，不会回头的。所以我们可以使用双指针来维护长度为 $k+1$的连续区间。这样能以$O(n)$的复杂度维护$nxt[i][0]$的内容。

//双指针维护
//第1个点的第k近的元素位置
int L=1,R=k+1;
//[L,R] 区间变化具有单调性，第i+1个点的区间L{i+1}>=L{i},R{i+1}>=R{i}
for(int i=2;i<=n;i++){
//求出第i个点第k近的元素位置 
while(R+1<=n && p[R+1]-p[i]<p[i]-p[L]){
  L++,R++;
} 

if(p[R]-p[i]>p[i]-p[L]) 
    //p[R]为第k小的元素;
    ;
else 
    //p[L]是第k小的元素
    ;
}

但是目前还是存在一个问题：空间大小。本题空间限制为 $125Mb$ ，若根据题意定义出的nxt二维数组会超空间。本题的步数$m$在给出后就不在发生变化，我们可以尝试压缩二维数组至一维。

观察之前求解的转移方程： $nxt[i][j]=nxt[nxt[i][j-1]][j-1]$ 。$2^j$步只由$2^{j-1}$步推出，可以尝试滚动数组压缩，且$m$固定，可在过程中更新 $m$ 的二进制位为$1$时的位置。

  int lg=log2(m);
  for(int i=0;i<=lg;i++){
    if((m>>i)&1){
      for(int j=1;j<=n;j++){
        ans[j]=nxt[ans[j]];
      }
    }
    //倍增：nxt[i][j]=nxt[nxt[i][j-1]][j-1]
    //节省空间压缩nxt空间为一维
    for(int j=1;j<=n;j++){
      tmp[j]=nxt[nxt[j]];
    }
    for(int j=1;j<=n;j++){
      nxt[j]=tmp[j];
    }
  }

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e6 + 5;
int n,k;//n个点，第k近
i64 m;//跳m次
i64 p[N];
int nxt[N];
int ans[N],tmp[N];
deque<int> q;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>k>>m;
  for(int i=1;i<=n;i++){
    cin>>p[i];
  }
  //求每个点第k近的元素，前k近的元素分布i的两侧,是一个连续区间,长度为k+1
  //双指针维护
  nxt[1]=k+1;//第1个点的第k近的元素位置
  int L=1,R=k+1;
  //[L,R] 区间变化具有单调性，第i+1个点的区间L{i+1}>=L{i},R{i+1}>=R{i}
  for(int i=2;i<=n;i++){
    //求出第i个点第k近的元素位置 
    while(R+1<=n && p[R+1]-p[i]<p[i]-p[L]){
      L++,R++;
    } 
    //p[R]为第k小的元素
    if(p[R]-p[i]>p[i]-p[L]) nxt[i]=R;
    else nxt[i]=L;//p[L]是第k小的元素
  }
  for(int i=1;i<=n;i++){
    ans[i]=i;
  }
  int lg=log2(m);
  for(int i=0;i<=lg;i++){
    if((m>>i)&1){
      for(int j=1;j<=n;j++){
        ans[j]=nxt[ans[j]];
      }
    }
    //倍增：nxt[i][j]=nxt[nxt[i][j-1]][j-1]
    //节省空间压缩nxt空间为一维
    for(int j=1;j<=n;j++){
      tmp[j]=nxt[nxt[j]];
    }
    for(int j=1;j<=n;j++){
      nxt[j]=tmp[j];
    }
  }
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<" ";
  }
  return 0;
}

[题解]ZAB-Frog