P15588 [KTSC 2026] 飞扬的松鼠 2 / Flying Squirrel 2

在二维平面上有一只飞扬的松鼠和 $N$ 根柱子。 我们将二维平面上的点表示为 $(x,y)$，其中横坐标 $x$ 代表向右的偏移，纵坐标 $y$ 代表向上的偏移。 柱子依次编号 $0\sim N-1$。柱子 $i$ 的底部位于 $(i,0)$，高度为无穷高。换言之，柱子 $i$ 是一条从 $(i,0)$ 出发，方向向上的射线。每根柱子要么是红色，要么是蓝色。若 $B[i]=0$，柱子 $i$ 是红色的；否则 $B[i]=1$，柱子 $i$ 是蓝色的。 在柱子以外的区域，松鼠向右水平飞行，维持现有高度不变。由于松鼠十分敏捷，向右飞行的时间视为 $0$。 当松鼠在柱子上时，松鼠可以将自己的高度改变 $1$，或者什么都不做。准确地说，在柱子 $i$ 的位置时，松鼠必须执行下列恰好一个操作： - **穿过**柱子。松鼠的高度不变，继续向右飞行。消耗时间为 $0$。 - **爬上**柱子。当且仅当柱子是红色的（$B[i]=0$）时可以执行该操作。松鼠的高度增加 $1$，然后继续向右飞行。消耗时间为 $A[i]$。 - **跳下**柱子。当且仅当柱子是蓝色的（$B[i]=1$）时可以执行该操作。松鼠的高度减少 $1$，然后继续向右飞行。消耗时间为 $A[i]$。 此外，当松鼠横坐标为 $i+0.5$（$0\le i\le N-1$）时，松鼠的高度必须在 $[L[i],R[i]]$ 间。当松鼠横坐标为 $N$ 时，松鼠的高度必须为 $H$。 令 $T[k]$ 为满足上述条件的情况下，松鼠用恰好 $k$ 次「跳下」操作到达 $(N,H)$ 所花费的时间最小值。若不存在这样的方案，令 $T[k]=-1$。 求出 $T[0],T[1],\cdots,T[H]$。 ### 实现细节 **这是一道函数式交互题**。你不必，也不应实现 `main` 函数。 你应当实现以下的函数： ```cpp vector fly(int H, vector A, vector B, vector L, vector R) ``` - $H$：松鼠的最终高度。 - $A,B,L,R$：大小为 $N$ 的整数数组。 - $B$：描述柱子颜色的数组。若 $B[i]=0$，柱子 $i$ 是红色的；否则 $B[i]=1$，柱子 $i$ 是蓝色的。 - 该函数必须返回一个大小为 $(H+1)$ 的数组 $T$。 - 该函数被调用恰好一次。 你的源代码中不应调用任何输入/输出函数。

样例评分程序的输入格式如下： * 第 $1$ 行：$N$ $H$ * 第 $2$ 行：$A[0]$ $A[1]$ $\ldots$ $A[N - 1]$ * 第 $3$ 行：$B[0]$ $B[1]$ $\ldots$ $B[N - 1]$ * 第 $4$ 行：$L[0]$ $L[1]$ $\ldots$ $L[N - 1]$ * 第 $5$ 行：$R[0]$ $R[1]$ $\ldots$ $R[N - 1]$

样例评分程序按以下格式打印答案： * 第 $1$ 行：$T[0]$ $T[1]$ $\ldots$ $T[H]$

### 数据范围 - $1\le N\le 200\, 000$； - $0\le H\le N$； - $0\le A[i]\le 10^9$； - $0\le B[i]\le 1$； - $0\le L[i]\le R[i] \le N$。 ### 子任务 | 编号 | 得分 | 限制 | | :-: | :-: | :- | | $1$ | $ 3$ | $N\le 300$ | | $2$ | $ 4$ | $A[i]=B[i]=0$ | | $3$ | $25$ | $B[i]=0$ | | $4$ | $20$ | $N\le 65\, 000, A[i]\le 5$ | | $5$ | $29$ | $N\le 65\, 000$ | | $6$ | $19$ | 无额外限制 | ### 样例 #### 样例 $1$ 考虑以下调用。 ``` fly(3, [8, 8, 2, 4], [1, 0, 1, 0], [1, 0, 2, 3], [1, 2, 2, 4]) ``` ::::align{center}  :::: 如果松鼠从柱子 $0$ 跳下并爬上柱子 $1$ 和 $3$，则满足条件。在这种情况下，跳跃次数为 $1$，耗时为 $20$ 秒。 ::::align{center}  :::: 如果松鼠从柱子 $0$ 和 $2$ 跳下并爬上柱子 $3$，则满足条件。在这种情况下，跳跃次数为 $2$，耗时为 $14$ 秒。 没有其他可能的方法。因此，函数应返回 [$-1$, $20$, $14$, $-1$]。 #### 样例 $2$ 考虑以下调用。 ``` fly(1, [1000000000], [0], [1], [1]) ``` 函数应返回 $[1000000000, -1]$。 #### 样例 $3$ 考虑以下调用。 ``` fly(3, [4, 7, 0, 3, 8, 4, 5], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 1, 2], [5, 1, 2, 5, 5, 6, 3]) ``` 函数应返回 $[7, -1, -1, -1]$。 #### 样例 $4$ 考虑以下调用。 ``` fly(7, [3, 3, 4, 1, 3, 2, 0, 1, 4, 3, 4, 0, 0, 1, 0, 4, 4, 5, 5, 0], [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1], [0, 0, 1, 1, 2, 1, 2, 2, 1, 1, 0, 1, 1, 3, 2, 2, 1, 6, 4, 4], [3, 2, 3, 3, 6, 2, 2, 4, 3, 4, 4, 5, 3, 6, 6, 5, 7, 8, 8, 9]) ``` 函数应返回 $[-1, 16, 11, 10, 9, 10, 12, 15]$。