题解 CF1523H Hopping Around the Array

\(\texttt{link}\)

题意

数轴上有 \(n\) 个点，每个点有属性 \(a_i\)，在第 \(i\) 个点可以花费 \(1\) 的步数移动至 \([i,i+a_i]\) 中任意一个点。定义一次操作为选出一个 \(i\)，使 \(a_i\gets a_i +1\)。

\(q\) 组询问，每次给出 \(l,r,k\)，求有 \(k\) 次操作机会时，从第 \(l\) 个点走到第 \(r\) 个点的最小步数。各组询问相互独立，即操作没有后效性。

\(1\le n,q\le 2\times 10^4,1\le a_i\le n,0\le k\le 30\)

题解

可以先想一个暴力，用 \(f_{i,j,k}\) 表示从 \(i\) 出发，走 \(j\) 步，至多操作了 \(k\) 次时能走到的最远点，查询时只需在 \(f_{l,x,k}\) 上二分 \(x\) 即可，依据是每次转移是连续的，跳到一个大于 \(r\) 的点必定可以跳到 \(r\)。

由此有转移方程 \(f_{i,j,k}=\max\limits_{k_1+k_2=k}\{\max\limits_{s=i}^{f_{i,j-1,k_1}}\{s+a_s+k_2\}\}\)，原因也是能从若 \(i\) 走到 \(x\)，那 \([i,x]\) 中的每个点都必定可以经过，即在其中取下一步的最远点，这个过程是 RMQ 问题，用 ST 表优化。

这样转移状态是 \(O(n^2 k)\) 的，发现查询时的二分本质上就是步数的倍增，我们只关注走了 \(2^j\) 步的情况，改变 \(f\) 定义，\(f_{i,j,k}\) 表示从 \(i\) 出发，走 \(2^j\) 步，至多操作了 \(k\) 次时能走到的最远点。转移方程为 \(f_{i,j,k}=\max\limits_{k_1+k_2=k}\{\max\limits_{s=i}^{f_{i,j-1,k_1}}f_{s,j-1,k_2}\}\)，初始化 \(f_{i,0,k}=i+a_i+k\)，直接枚举 \(k_1,k_2\) 转移，用 ST 表可做到 \(O(nk^2\log n+nk\log^2n)\) 预处理。

对于每次询问，类似倍增求树上 \(k\) 级祖先，从 \(\log n\) 位开始从大到小考虑，令 \(g_{j,k}\) 表示考虑完 \([j,\log n]\) 位，至多操作了 \(k\) 次时，\(l\) 能去到最远位置，若对于所有 \(k\)，均满足 \(\max\limits_{k_1+k_2=k}\{\max\limits_{s=l}^{g_{j+1,k_1}}f_{s,j,k_2}\}< r\)，说明不存在任何转移方式可以通过这 \(2^j\) 步走到 \(r\)，换言之这 \(2^j\) 步是必走的，于是答案加上 \(2^j\)，并更新 \(g_{j,k}=\max\limits_{k_1+k_2=k}\{\max\limits_{s=i}^{g_{j+1,k_1}}f_{s,j,k_2}\}\)，否则这 \(2^j\) 步是不必要的，答案不变，并让 \(g_{j,k}=g_{j+1,k}\)。

你发现每次询问都要预处理 \(\log n\) 次 ST 表，单次查询复杂度是糟糕的 \(O(nk\log^2 n)\)，但是对于每组询问，\(f\) 是不变的，不必每次都预处理，于是把询问离线下来，对于每个 \(j\) 把每组询问都更新一遍即可。

总时间复杂度 \(O((n+q)(k^2\log n+k\log^2n))\)，空间复杂度 \(O(nk\log n)\)。

注意空间访问尽量连续，不知道会不会卡常。