编号为 1~n 的 n 个点. 编号为 i 的点可以跳到编号为 [max(i-xi,1), min(i+xi,n)] 的点. 定义 i,j 的距离为 min(i跳到j的最小步数, j跳到i的最小步数). 求两点间的最大距离. (1≤n≤10^5, 1≤xi<n) 跳 k 步可以到的范围是一个区间.
O(n^2) 暴力: 枚举起点, 进行 BFS. 由于能扩展, 已扩展到的点都是区间, 所以很容易检查应该将哪些点入队. 单次 O(n).
看起来可以倍增的样子 QAQ
设 [l[k][i], r[k][i]] 为从点 i 出发跳 2^k 步能到达的范围. r[k+1][i] = max { r[k][j] | l[k][i] ≤ j ≤ r[k][i] }, l[k+1][i] 同理. 对每一层建线段树即可 O(n lg^2 n) 预处理.
不妨二分答案. 如果存在两点 i,j 使得 i 无法用 k 步到达 j, 且 j 无法用 k 步到达 i, 那么 dis(i,j) > k, 从而最大距离 > k.
方便起见, 不做通常意义上的二分, 而是按二进制从高位往低位确定答案. 那么, 可以用 O(nlg n) 的时间处理出每个点跳 x 步可以到达的范围. 需要检查: 是否存在 i,j, 使得 r[i] < j, l[j] > i. 固定 j, 只用检查是否存在 i∈[1,l[j]), 使得 r[i] < j. 求 r 的前缀最小值即可. 如果存在, 说明答案 > x, 把处理出来的范围数组复制一份.
我们始终维护答案 > x的循环不变式, 因此, 确定出来的数+1是我们想要的.