← 返回题目列表

Codeforces · 1076/G

G. 阵列游戏

中文机器翻译题面 查看原题

考虑两个玩家之间的以下游戏:

有一个数组 $$$b_1$$$, $$$b_2$$$, ..., $$$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$$$ — 对于 [l, r]$$$ 中的每个 $$$i \,将 $$$a_i$$$ 增加 $$$d$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ — 告诉谁是在 $$$a$$$ 子数组上从索引 $$$l$$$ 到索引 $$$r$$$ 进行的游戏的获胜者。假设双方都选择最优策略。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$, $$$1 \le m \le 5$$$) — 分别是 $$$a$$$ 中的元素数量、游戏中描述的参数和查询次数。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$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$$$ 。

示例

输入 #1

5 2 4
1 2 3 4 5
1 3 5 6
2 2 5
1 1 2 3
2 1 5

输出 #1

1
1

输入 #2

5 1 3
1 1 3 3 4
2 1 5
2 2 5
2 3 5

输出 #2

1
2
1