P17738 [ICPC 2019 Xuzhou R] Yuuki and a problem

Yuuki 是一名可爱且具有出色麻将天赋的高中生，她提出了一个很酷的问题。问题描述如下： 给定一个包含 $N$ 个整数的序列 $a_1, a_2, \cdots, a_N$ 和 $Q$ 次操作。操作共有两种类型。 - 修改操作：给定 $x, y$，将 $a_x$ 改为 $y$。 - 查询操作：给定 $L, R$。将 $a_L, a_{L + 1}, \cdots, a_{R}$ 视为面值分别为 $a_L, a_{L + 1}, \cdots, a_{R}$ 的硬币，请找出最小的数字 $yuuki$，使得无法从上述硬币中选出一个子集，使得子集中硬币面值之和恰好等于 $yuuki$。

第一行包含两个整数 $N, Q$，分别表示序列的长度和操作的次数。 接下来一行包含 $N$ 个由空格分隔的整数 $a_1, a_2, \cdots, a_N$。 再接下来 $Q$ 行描述操作。每行一定符合以下两种格式之一： 1. `1 x y`：修改操作。 2. `2 L R`：查询操作。 各个变量的含义如问题描述所述！ - $1 \le N, Q, a_i \le 2 \times 10^5$ - $1 \le x \le N$ - $1 \le y \le 2 \times 10^5$ - $1 \le L \le R \le N$

对于每个查询操作，在一行中输出对应的 $yuuki$ 值。

翻译由 DeepSeek V4 Pro 完成