← 返回题目列表

Codeforces · 1217/E

E. 求和查询?

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

让我们按以下方式定义平衡多重集。以十进制表示形式写下多重集所有元素的总和。对于该数字的每个位置,检查多重集是否包含至少一个元素,使得该元素的数字与该位置处的总和的数字相同。如果每个位置都成立,则多重集是平衡的。不然就不平衡了。

例如,多重集 $$$\{20, 300, 10001\}$$$ 是平衡的,多重集 $$$\{20, 310, 10001\}$$$ 是不平衡的:

红色数字标记元素以及这些元素与总和具有相同数字的位置。第一个多重集合的总和是$$$10321$$$,每个位置都有所需的数字。第二个多重集的总和是 $$$10331$$$ 并且倒数第二个数字没有出现在任何数字中,从而使多重集不平衡。

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 整数组成。

系统会要求您对其执行一些查询。查询可以有两种类型:

- $$$1~i~x$$$ — 将 $$$a_i$$$ 替换为值 $$$x$$$;
- $$$2~l~r$$$ — 找到数字 $$$a_l, a_{l + 1}, \dots, a_r$$$ 的多重集的不平衡子集,其总和最小,或者报告不存在不平衡子集。

请注意,空多重集是平衡的。

对于第二类型的每个查询,打印不平衡子集的最低总和。如果不存在不平衡子集,则打印 -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。

示例

输入 #1

4 5
300 10001 20 20
2 1 3
1 1 310
2 1 3
2 3 3
2 3 4

输出 #1

-1
330
-1
40

注意

多重集 $$$\{20, 300, 10001\}$$$ 的所有子集都是平衡的,因此答案为 -1。

第三个查询中可能的不平衡子集是 $$$\{20, 310\}$$$ 和 $$$\{20, 310, 10001\}$$$。最小的总和是 $$$\{20, 310\}$$$。请注意,系统会要求您选择一个子集,而不是子段,因此所选元素可能不会在数组中相邻。

第四个查询仅包含空子集和子集$$$\{20\}$$$。两者都是平衡的。

最后一个查询包括空子集和子集 $$$\{20\}$$$、$$$\{20\}$$$ 和 $$$\{20, 20\}$$$。只有$$$\{20, 20\}$$$是不平衡的,它的总和是$$$40$$$。请注意,系统会要求您选择一个多重集,因此它可能包含相同的元素。