题目分析

我们有 N 个岛屿，从每个岛屿 i 可以：

• 简单跳跃：i → i+1
• 困难跳跃：i → v_i (i < v_i ≤ N)

约束条件：对任意 i < j，要么 v_i ≤ j，要么 v_j ≤ v_i。

需要计算从每个岛屿出发，最多 K 次跳跃能到达的不同岛屿数量。

---

核心思路

1. 关键性质

题目给出的约束条件：

对于任意 i < j，要么 v_i ≤ j，要么 v_j ≤ v_i

这个条件非常重要，它意味着 v 数组具有单调栈的性质。

实际上，这个条件等价于：v 数组的每个后缀最小值序列是单调的。

---

2. 问题转化

设 f[i] 表示从岛屿 i 出发，到达岛屿 n 所需的最小跳跃次数。

则状态转移为：

f[i] = min(f[i+1], f[v_i]) + 1

因为从 i 可以跳到 i+1 或 v_i，都需要一次跳跃。

---

3. 算法设计

3.1 动态规划

从后往前计算 f[i]：

• 初始化 f[n] = 0（不需要跳跃）
• 对于 i = n-1, n-2, ..., 1：

  f[i] = min(f[i+1], f[v_i]) + 1
  

3.2 分块优化

由于 N 可达 3e5，直接计算每个起点的可达集合不可行。

代码采用分块方法：

• 将岛屿分成大小为 B ≈ √n 的块
• 每块内维护 f 值的有序数组
• 支持区间更新和查询操作

3.3 核心操作

1. reb(u, w)：在块内重新插入元素 u 并设置 f[u] = w
2. upd(l, w)：更新区间 [l, n] 的 f 值（加 w）
3. query(l, w)：查询从 l 开始，f 值 ≤ w 的岛屿数量

---

4. 算法流程

1. 初始化：

   • f[n] = 0，其他 f[i] = ∞
   • 分块，每块内按 f 值排序

2. 反向DP：

   • 从 i = n-1 到 1：
     • 计算 D = f[v_i] + 偏移量
     • 更新当前岛屿 i 的 f 值
     • 更新 v_i 到 n 的 f 值
     • 查询从 i 出发，f 值 ≤ K 的岛屿数量

3. 输出：每个岛屿的答案 F[i]

---

5. 复杂度分析

• 分块大小：B = O(√n)
• 每次更新：O(√n log n)
• 总复杂度：O(n√n log n)

对于 n = 3e5，√n ≈ 550，可以接受。

---

6. 样例验证

样例 1

输入：n=5, K=1, v=[4,3,4,5]
处理：
- f[5]=0
- i=4: f[4]=min(f[5])+1=1
- i=3: f[3]=min(f[4],f[4])+1=2  
- i=2: f[2]=min(f[3],f[3])+1=3
- i=1: f[1]=min(f[2],f[4])+1=2
然后计算每个起点在1步内能到达的岛屿数。
输出：3 2 2 2 1

样例 2

输入：n=6, K=2, v=[2,3,5,5,6]
类似处理，得到输出：3 4 4 3 2 1

---

7. 关键优化

7.1 分块排序

每块内维护 f 值的有序数组，支持快速区间查询。

7.2 懒标记

对整块的更新使用懒标记，避免逐个修改。

7.3 二分查找

在有序块内使用二分查找统计满足条件的元素数量。

---

算法标签

• 分块 (Square Root Decomposition)
• 动态规划 (Dynamic Programming)
• 单调性 (Monotonicity)
• 区间查询 (Range Query)

---

总结

本题通过分析题目给出的特殊约束条件，发现 v 数组的单调性质，从而设计出从后往前的动态规划算法。利用分块技术优化大规模区间操作，在 O(n√n log n) 时间内解决了问题。核心在于将复杂的跳跃关系转化为简洁的 DP 转移，并用分块平衡查询和更新的复杂度。