← 返回题目列表

Codeforces · 794/F

F. Leha 和安全系统

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

Bankopolis,你已经知道的城市,终于有一家新银行开业了!不幸的是,它的安全系统还不能正常工作……与此同时,黑客Leha抵达Bankopolis并决定测试该系统!

银行有 n 个存放客户资金的单元格。由 n 个数字 a1、a2、...、an 组成的序列描述了每个客户拥有的金额。 Leha 想要向银行的数据库发出请求,找出序列的某些子段上的总金额并更改某些子段上的序列值。利用系统中的错误,Leha 可以向数据库请求两种类型的查询:

- 1 l r x y 表示 Leha 将序列 ai 的每个元素中的每个数字 x 更改为数字 y,其中 l ≤ i ≤ r 成立。例如,如果我们将数字 11984381 的数字 8 更改为 4,我们将得到 11944341。值得注意的是,Leha 为了保持在阴影中,从不将数据库中的数字更改为 0,即 y ≠ 0。
- 2 l r 表示 Leha 要求计算并打印序列 ai 中这些元素的总和,其中 l ≤ i ≤ r 成立。

由于Leha是一名白帽黑客,他不想在真实的数据库上测试此漏洞。你要写一个类似的数据库供Leha 测试。

输入

输入的第一行包含两个整数 n 和 q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105),分别表示银行中的单元格数量和查询总数。

下面一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai < 109) 表示每个单元格中最初的金额。这些整数不包含前导零。

以下 q 行均具有以下格式之一:

- 1 l r x y (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 9, 1 ≤ y ≤ 9),表示Leha要求更改序列中每个元素ai的数字y上的每个数字x,其中l ≤ i ≤ r成立;
- 2 l r (1 ≤ l ≤ r ≤ n),表示您必须计算并打印 l ≤ i ≤ r 成立的元素 ai 的总和。

输出

对于每个第二种类型的查询,打印一个表示所需总和的数字。

示例

输入 #1

5 5
38 43 4 12 70
1 1 3 4 8
2 2 4
1 4 5 0 8
1 2 5 8 7
2 1 5

输出 #1

103
207

输入 #2

5 5
25 36 39 40 899
1 1 3 2 7
2 1 2
1 3 5 9 1
1 4 4 0 9
2 1 5

输出 #2

111
1002

注意

让我们看一下示例测试用例。

最初的序列是 [38, 43, 4, 12, 70]。

第一次更改后,对于索引在区间 [1; 中的每个元素,等于 4 的每个数字变为 8 3]。因此,新序列是[38,83,8,12,70]。

第一个 sum 查询的答案是区间 [2; 中的和。 4],等于 83 + 8 + 12 = 103,因此该查询的答案是 103。

第二次更改后序列变为 [38, 83, 8, 12, 78],第三次更改后序列变为 [38, 73, 7, 12, 77]。

第二个求和查询的答案是 38 + 73 + 7 + 12 + 77 = 207。