题目描述

Klimi 和 Nikol 有一个长度为 N 的整数数组 A，下标从 0 到 N-1，且数组中的所有元素两两不同。

她们用一个棋子在数组上玩游戏。初始时，棋子位于某个格子中。每一步操作如下：

1. 当前行动的玩家把棋子从当前位置 x 移动到另一个位置 y。要求：

   • 0 <= y < N
   • x != y
   • |y - x| <= D

   也就是说，玩家必须移动棋子，并且每次最多移动 D 个位置。

2. 当棋子移动到位置 y 后，该玩家将 A_y 加到自己的得分中。

两位玩家轮流行动，Klimi 先手。游戏恰好进行 10^100 轮后结束，此时总分更高者获胜；如果两人总分相同，则 Klimi 获胜。

你需要处理若干次操作，操作分为两类：

• 修改：修改数组中的某一个值；
• 询问：给定棋子的初始位置，判断双方都采取最优策略时，先手 Klimi 是否获胜。

修改会永久生效，也就是说，每次询问都要基于之前所有修改后的当前数组来回答。

实现要求

你需要实现下面三个函数：

void init(std::vector<int> A, int D);
void updateValue(int index, int newValue);
bool isWinning(int startIndex);

函数说明

init

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

该函数只会在每组测试开始时调用一次，用于提供初始数组 A 和参数 D。

updateValue

void updateValue(int index, int newValue)

处理一次修改操作，将 A[index] 设为 newValue。

保证修改后数组中的所有值仍然两两不同。

isWinning

bool isWinning(int startIndex)

处理一次询问：若棋子一开始位于 startIndex，双方都最优，先手 Klimi 是否能够获胜。

• 若能获胜，返回 true；
• 否则返回 false。

代码要求

你的程序必须：

• 实现上述三个函数；
• 不能包含 main 函数；
• 不能从标准输入读取，也不能向标准输出打印；
• 必须包含头文件：

#include "game.h"

在满足这些条件的前提下，你可以自由定义辅助函数、变量、常量等。

本地评测

系统提供文件 Lgrader.cpp 和 game.h，你可以将其与你的代码一起编译进行本地测试。

本地评测器输入格式

• 第 1 行：两个整数 N, D
• 第 2 行：A_0 A_1 ... A_{N-1}
• 第 3 行：一个整数 Q
• 接下来 Q 行：每行一个操作，格式如下：

1. 1 ind val：修改操作，将 A[ind] 设为 val
2. 2 ind：询问操作，询问棋子起始位置为 ind 时，isWinning(ind) 的返回值

对于每个类型为 2 的操作，本地评测器会输出：

• 若函数返回 false，输出 0；
• 若函数返回 true，输出 1。

约束条件

• 1 <= N, Q <= 2 * 10^5
• 1 <= D <= 25
• 1 <= A_i <= 10^9
• 0 <= index, startIndex < N
• 1 <= newValue <= 10^9
• 任意时刻（包括所有修改之后），数组 A 中的值始终两两不同。

子任务

子任务	分值	N, Q	D	额外限制
1	8	<= 10	<= 25	无
2	18	<= 2 * 10^3		没有修改操作
3	16	<= 2 * 10^5
4	27	<= 10^5	<= 10	无
5	31	<= 2 * 10^5	<= 25

你必须通过某个子任务中的全部测试点，才能获得该子任务的分数。

样例

设 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]。

在本地评测器中的输入输出如下：

输入

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

输出

1
0
0
1