#P5226. [Lydsy2017省队十连测]永远

[Lydsy2017省队十连测]永远

[Lydsy2017省队十连测] 永远

题目描述

给定一个长度为 nn 的序列,支持以下三种区间操作:

  • 1 l r:将区间 [l,r][l,r] 中的每个数平方。
  • 2 l r:将区间 [l,r][l,r] 中的每个数开方,取非负实数平方根,操作过程中不取整。
  • 3 l r:查询区间 [l,r][l,r] 中所有数分别与 10810^8 取较小值后的和,即 ∑i=lrmin⁡(ai,108)\sum_{i=l}^{r}\min(a_i,10^8)。

查询的求和结果取最近的整数后输出。平方与开方操作作用于序列的实际值;10810^8 的截断用于查询。

输入格式

从标准输入读入。

第一行两个正整数 n,mn,m。

第二行 nn 个正整数,表示初始序列。

接下来 mm 行,每行三个整数 op,l,rop,l,r,描述一次操作。

输出格式

向标准输出对每个 3 操作写出一行,表示对应查询结果取最近整数后的值。

样例

样例输入

4 4
23333 66666 79520 99983
2 2 3
3 1 3
1 3 4
3 2 4

样例输出

23873
100079778

数据范围

测试点 nn mm 特殊性质
1 1000010000 无
2 120000120000 只有操作 3
3 160000160000
4 110000110000 只存在两种操作
5 130000130000
6 150000150000
7 170000170000 操作 3 的次数不超过 500
8 100000100000 无
9 140000140000
10 180000180000