1240. hard query problem

scnucjh 遇到一个问题,由于他太菜,所以他向 Z3L5M 请教。

这个问题是这样的:

函数是 f(x) 表示 x 各个数位的和,例如, f (1) = 1,f (10) = 1, f (19) = 10, f (222) = 6

现在给定一个长度为 n 的数组,每个数的值分别为 a_1, a_2 , ..., a_n 。现在给出 m 个操作,一共有两种不同的操作:

  • 1 操作:给定 L,R,将闭区间 [L, R] 里面的每个数作用 f (x)
  • 2 操作:给定 L,R,求闭区间 [L, R] 里面的数的最小值

由于 Z3L5M 忙着写论文,所以现在这个问题交到你手上了。

输入

输入的第一行有两个整数 n,m(1 ≤ n, m ≤ 100000)

第二行有 n 个整数,分别表示 a_1 , a_2, ..., a_n(1 ≤ a_i ≤ 10^{18} )

接下来 m 行,每行三个整数 o, L, R (1 ≤ o ≤ 2, 1 ≤ L ≤ R ≤ n), 分别表示操作的类型,还有操作区间 L,R

输出

对于每个 2 操作,输出一行表示 [L, R] 内的最小值。

样例

标准输入 复制文本
5 9
6666666666666666 6666666666666666 233333333333 23333333 2333
2 1 2
2 1 3
2 1 5
1 3 3
2 1 5
1 1 5
2 1 5
1 1 1
2 1 2
标准输出 复制文本
6666666666666666
233333333333
2333
35
8
15

提示

  • 第 4 个操作之后数组变成 [6666666666666666, 6666666666666666, 35, 23333333, 2333].
  • 第 6 个操作之后数组变成 [96,96,8, 23, 11].
  • 第 8 个操作之后数组变成 [15, 96, 8, 23, 11].

来源

2019 SCNUCS-N 现场赛

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 28
通过 6