题目描述

Klimi 和 Nikol 有一个整数数组 $A$，它包含 $N$ 个格子，编号从 $0$ 到 $N-1$，且包含不同的整数值。女孩们正在玩一个游戏，使用一个在数组上移动的棋子。初始时，棋子位于某个格子。游戏的一步按照以下过程进行：

• 轮到行动的玩家拿起棋子，将其移动到距离当前格子至多 $D$ 的另一个格子。形式化地，如果棋子当前在格子 $x$ ($0\leq x< N$)，则允许玩家将棋子移动到格子 $y$ ($0\leq y<N$)，如果 $|y-x|\leq D$ 且 $x\neq y$。注意这意味着玩家必须移动棋子。
• 将棋子移动到某个格子 $y$ 后，玩家将 $A_y$ 加到她的分数中。注意分数是在移动棋子之后增加的。

移动在两名女孩之间交替进行，Klimi 先手。游戏在恰好 $10^{100}$ 回合后结束，届时总分较高的女孩获胜。如果分数相等，则 Klimi 获胜。

女孩们对完成一局游戏所需的时间并不十分满意，因此她们请你仅需计算不同场景下的最优玩法结果。

形式化地，你将得到初始数组 $A$ 和值 $D$，然后你需要处理 $Q$ 个两种类型的询问：

• 更新：数组中的一个值被改变。
• 询问：给定棋子的某个初始位置，假设双方均采取最优策略，问 Klimi（先手者）是否赢得游戏。

更新在询问之间持续存在，因此每个询问必须在考虑迄今为止发生的所有更新的情况下回答。

实现细节部分更详细地描述了你需要支持的接口。

实现细节

你必须实现三个函数。你的第一个函数 init 必须具有以下原型：

void init(std::vector<int> A, int D)

它将在测试开始时被调用一次，向你提供数组 $A$ 和值 $D$。

你的另外两个函数 updateValue 和 isWinning 必须具有以下原型：

void updateValue(int index, int newValue)

bool isWinning(int startIndex)

对这两个函数的调用总次数为 $Q$（参见约束部分），且所有调用将在调用 init 之后进行。

updateValue 函数必须处理更新询问，并将 $A_{index}$ 设置为 newValue。保证每次更新后 $A$ 中的所有值仍然互不相同。

isWinning 函数必须处理询问，如果 Klimi 在给定棋子起始于 startIndex 的情况下能在当前数组上获胜，则返回 true，否则返回 false。

你的程序必须实现这三个函数，但不应包含 main 函数。同时，它不得从标准输入读取数据或向标准输出打印内容。你的程序还必须通过预处理指令包含头文件 game.h：#include "game.h"

只要遵守这些条件，你的程序可以包含任何辅助函数、变量、常量等。

本地测试

提供了文件 Lgrader.cpp 和 game.h，你可以将它们与你的代码一起编译进行测试。

输入格式

评测器的输入格式为：

• $N$ $D$
• $A_0$ $A_1$ ... $A_{N-1}$
• $Q$
• <$Q$ 行询问>

其中询问的格式为：

• $1$ ind val --- 更新询问，设置 $A_{\mathrm{ind}}=\mathrm{val}$
• $2$ ind --- 询问，棋子起始于 ind

输出格式

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

6 2
1 7 4 9 30 2
5
2 0
2 1
1 4 8
2 0
2 1

1
0
0
1

提示

样例

假设 $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$ 中的值在任何时候均互不相同，包括更新之后。

子任务

你必须通过某个子任务中的所有测试才能获得该子任务的分数。

翻译由 DeepSeek V4 Pro 完成