CF1217E Sum Queries?

我们这样定义一个“平衡多重集”：将多重集所有元素的和写成十进制表示。对于该数字的每一位，检查多重集中是否存在至少一个元素，使得该元素在对应位置上的数字与和在该位置上的数字相同。如果每一位都满足这个条件，则该多重集是平衡的；否则就是不平衡的。 例如，多重集 $\{20, 300, 10001\}$ 是平衡的，而多重集 $\{20, 310, 10001\}$ 是不平衡的：  红色数字标记了那些元素及其在和中与之相同的数字位置。第一个多重集的和为 $10321$，每一位都存在对应的元素数字。第二个多重集的和为 $10331$，倒数第二位的数字没有在任何元素中出现，因此该多重集是不平衡的。 现在给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \dots, a_n$。 你需要对其进行若干次操作，操作有两种类型： - $1~i~x$ —— 将 $a_i$ 替换为 $x$； - $2~l~r$ —— 在多重集 $a_l, a_{l+1}, \dots, a_r$ 的所有子集（可以包含重复元素）中，找出和最小的不平衡子集，并输出其和。如果不存在不平衡子集，则输出 $-1$。 注意，空多重集是平衡的。 对于每个第二类操作，输出不平衡子集的最小和。如果不存在不平衡子集，则输出 $-1$。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示数组的元素个数和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i < 10^9$）。 接下来的 $m$ 行，每行表示一个操作，格式如下： - $1~i~x$（$1 \le i \le n$，$1 \le x < 10^9$）——将 $a_i$ 替换为 $x$； - $2~l~r$（$1 \le l \le r \le n$）——在 $a_l, a_{l+1}, \dots, a_r$ 的所有子集（多重集）中，找出和最小的不平衡子集，或报告不存在。 保证至少有一个第二类操作。

对于每个第二类操作，输出不平衡子集的最小和。如果不存在不平衡子集，则输出 $-1$。

对于多重集 $\{20, 300, 10001\}$ 的所有子集都是平衡的，因此答案为 $-1$。 第三个操作中，可能的不平衡子集有 $\{20, 310\}$ 和 $\{20, 310, 10001\}$，其中和最小的是 $\{20, 310\}$。注意你需要选择的是子集，而不是子区间，因此选中的元素不一定相邻。 第四个操作只包含空集和 $\{20\}$，它们都是平衡的。 最后一个操作包含空集、$\{20\}$、$\{20\}$ 和 $\{20, 20\}$。只有 $\{20, 20\}$ 是不平衡的，其和为 $40$。注意你需要选择的是多重集，因此可以包含相同的元素。 由 ChatGPT 4.1 翻译