P16391 [IATI 2024] Game

Klimi 和 Nikol 有一个整数数组 $A$，它包含 $N$ 个格子，编号从 $0$ 到 $N-1$，且包含**不同**的整数值。女孩们正在玩一个游戏，使用一个在数组上移动的棋子。初始时，棋子位于某个格子。游戏的一步按照以下过程进行： - 轮到行动的玩家拿起棋子，将其移动到距离当前格子至多 $D$ 的另一个格子。形式化地，如果棋子当前在格子 $x$ ($0\leq x< N$)，则允许玩家将棋子移动到格子 $y$ ($0\leq y

评测器的输入格式为： - $N$ $D$ - $A_0$ $A_1$ ... $A_{N-1}$ - $Q$ - 其中询问的格式为： - $1$ `ind` `val` --- 更新询问，设置 $A_{\mathrm{ind}}=\mathrm{val}$ - $2$ `ind` --- 询问，棋子起始于 `ind`

对于每个类型 $2$ 的询问，评测器会打印 $0$ 如果你的函数返回 `false`，打印 $1$ 如果返回 `true`。

### 样例 假设 $A = [1, 7, 4, 9, 30, 2]$，$D = 2$，$Q = 5$。一个调用的序列示例为： - 调用 `init({1, 7, 4, 9, 30, 2}, 2)` - 调用 `isWinning(0)` 返回 `true` - 调用 `isWinning(1)` 返回 `false` - 调用 `updateValue(4, 8)` - 调用 `isWinning(0)` 返回 `false` - 调用 `isWinning(1)` 返回 `true` 更新调用后的数组为 $[1, 7, 4, 9, 8, 2]$。可以证明，如果两位女孩均采取最优玩法，上述回答均是正确的。 ### 数据范围 - $1 \leq N, Q \leq 2\cdot 10^5$ - $1 \leq D \leq 25$ - $1 \leq A_i \leq 10^9$ - $0 \leq \mathrm{index}, \mathrm{startIndex} < N$ - $1 \leq \mathrm{newValue} \leq 10^9$ - $A$ 中的值在任何时候均互不相同，包括更新之后。 ### 子任务 | **子任务** | **分数** | **$N, Q$** | **$D$** | **额外约束** | | :---: | :---: | :---: | :---: | :---: | | $1$ | $8$ | $N, Q \leq 10$ | $D \leq 25$ | | | $2$ | $18$ | $N, Q \leq 2\cdot 10^3$ | $D \leq 25$ | 没有更新询问 | | $3$ | $16$ | $N, Q \leq 2\cdot 10^5$ | $D \leq 25$ | 没有更新询问 | | $4$ | $27$ | $N, Q \leq 10^5$ | $D \leq 10$ | | | $5$ | $31$ | $N, Q \leq 2\cdot 10^5$ | $D \leq 25$ | | 你必须通过某个子任务中的所有测试才能获得该子任务的分数。 翻译由 DeepSeek V4 Pro 完成