CF1076G Array Game

考虑如下的两人游戏： 有一个由正整数组成的数组 $b_1, b_2, \ldots, b_k$。最开始，一个棋子放在数组的第一个格子里，并且 $b_1$ 减 $1$。两位玩家轮流行动。每一回合，当前玩家需要执行以下操作：假设棋子当前在第 $x$ 个格子，那么他需要选择一个 $y \in [x, \min(k, x + m)]$，满足 $b_y > 0$，然后将棋子移动到第 $y$ 个格子，并将 $b_y$ 减 $1$。如果无法进行有效的移动，则当前玩家输掉游戏。 你的任务如下：给定一个由 $n$ 个正整数组成的数组 $a$，以及 $q$ 个对其的操作。操作有两种类型： - $1\ l\ r\ d$ —— 对于每个 $i \in [l, r]$，将 $a_i$ 增加 $d$； - $2\ l\ r$ —— 问如果在 $a$ 的第 $l$ 到第 $r$ 个元素组成的子数组上进行上述游戏，假设双方都采取最优策略，谁会获胜。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, q \le 2 \times 10^5$，$1 \le m \le 5$），分别表示数组 $a$ 的长度、游戏中的参数 $m$ 以及操作的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{12}$），表示数组 $a$ 的元素。 接下来 $q$ 行，每行表示一个操作。操作有两种类型。第一种操作为 $1\ l\ r\ d$（$1 \le l \le r \le n$，$1 \le d \le 10^{12}$），表示对于每个 $i \in [l, r]$，将 $a_i$ 增加 $d$。第二种操作为 $2\ l\ r$（$1 \le l \le r \le n$），表示你需要判断如果在 $a$ 的第 $l$ 到第 $r$ 个元素组成的子数组上进行游戏，谁会获胜。 保证至少有一个类型为 $2$ 的操作。

对于每个类型为 $2$ 的操作，输出一行。如果对应游戏中先手获胜，输出 $1$；否则输出 $2$。

由 ChatGPT 4.1 翻译